【FJWC 2019】森林

古城微笑少年丶 2021-12-20 10:21 139阅读 0赞

## 【FJWC 2019】 森林 ##

![img][]

### 样例输入 ###

0  
5  
1 0 0 2

### 样例输出 ###

1  
2  
3  
3

我们发现，答案就是直径加上直径上某个点出发，不经过其他直径上的点的最长链。这里的直径可以是任意一条直径。

首先我们每次只加一个点，所以我们很好维护新的直径。假设旧直径的两个端点是\\((A,B)\\)，则加入点\\(X\\)后新的端点可能是\\((A,B),(A,X),(B,X)\\)。

然后我们考虑求“直径上某个点出发，不经过其他直径上的点的最长链”。

我们知道，\\(Lct\\)有虚边和实边。我们给每个节点开一个\\(multiset\\)维护虚子树贡献的最长链。

我们记录\\(mx\_v\\)表示\\(v\\)所在\\(splay\\)中所有虚儿子贡献的最长链。\\(lmx\_v\\)表示\\(v\\)所在\\(splay\\)的从最左端点出发，经过一段实边，再经过一段虚边的最长路径；\\(rmx\_v\\)同理。

很显然，\\(v\\)所在这条实链的顶端到子树内的最长链就是\\(lmx\_v\\)。记录\\(lmx\_v\\)是为了在\\(access\\)操作的时候维护向其父亲贡献的最长链。

我们询问的时候就先\\(MakeRoot(A)\\),再\\(access(B)\\)，这样\\(A\\to B\\)的直径在一条实链上，答案就是\\(dis\_\{A,B\}+mx\_A-\[mx\_A!=0\]\\)。

因为有\\(MakeRoot\\)操作，所以我们要维护\\(rmx\\)，\\(reverse\\)的时候还要交换\\(lmx,rmx\\)。  
可以参考[【清华集训2016】数据交互][2016]

**注意**：\\(push\\\_down(v)\\)的时候要将左右儿子的\\(lmx\\)和\\(rmx\\)也交换了，否则\\(update\\)的时候会出错。

代码：

#include<bits/stdc++.h>
    #define ll long long
    #define N 400005
    
    using namespace std;
    inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
    
    multiset<int>st[N];
    int n;
    int ans;
    int A,B;
    int rev[N],fa[N],ch[N][2];
    int lmx[N],rmx[N],mx[N];
    int size[N];
    #define ls ch[v][0]
    #define rs ch[v][1]
    
    void update(int v) {
        size[v]=size[ls]+size[rs]+1;
        mx[v]=max(*(--st[v].end()),max(mx[ls],mx[rs]));
        lmx[v]=*(--st[v].end())+size[ls];
        rmx[v]=*(--st[v].end())+size[rs];
        lmx[v]=max(lmx[v],lmx[ls]);
        rmx[v]=max(rmx[v],rmx[rs]);
        if(rs) lmx[v]=max(lmx[v],lmx[rs]+size[ls]+1);
        if(ls) rmx[v]=max(rmx[v],rmx[ls]+size[rs]+1);
    }
    
    void Rev(int v) {
        rev[v]^=1;
        swap(ls,rs);
        swap(lmx[v],rmx[v]);
    }
    
    void down(int v) {
        if(rev[v]) {
            /*************/
            Rev(ls);
            Rev(rs);
            rev[v]=0;
        }
    }
    
    bool isroot(int v) {return v!=ch[fa[v]][0]&&v!=ch[fa[v]][1];}
    
    void rot(int v) {
        int f=fa[v],gr=fa[f];
        int sn=v==ch[f][1],son=ch[v][!sn];
        if(!isroot(f)) ch[gr][f==ch[gr][1]]=v;
        ch[f][sn]=son;
        ch[v][!sn]=f;
        if(son) fa[son]=f;
        fa[v]=gr;
        fa[f]=v;    
        update(f);
        update(v);
    }
    
    void Splay(int v) {
        static int st[N],top;
        top=0;
        st[++top]=v;
        for(int i=v;!isroot(i);i=fa[i]) st[++top]=fa[i];
        while(top) down(st[top--]);
        while(!isroot(v)) {
            int f=fa[v],gr=fa[f];
            if(!isroot(f)) rot(v==ch[f][1]^f==ch[gr][1]?v:f);
            rot(v);
        }
    }
    
    void Insert(int v,int f) {st[f].insert(lmx[v]+1);}
    void Del(int v,int f) {st[f].erase(st[f].find(lmx[v]+1));}
    
    void access(int v) {
        int tem=0;
        while(v) {
            Splay(v);
            if(tem) Del(tem,v);
            if(rs) Insert(rs,v);
            rs=tem;
            update(v);
            tem=v;
            v=fa[v];
        }
    }
    
    void Make_root(int v) {
        access(v);
        Splay(v);
        Rev(v);
    }
    
    void Link(int v,int f) {
        update(v);
        access(f);
        Splay(f);
        fa[v]=f;
        Insert(v,f);
        update(f);
    }
    
    namespace DIS {
        int dep[N],fa[N][20];
        int mxdis=0;
        int lca(int a,int b) {
            if(dep[a]<dep[b]) swap(a,b);
            for(int i=18;i>=0;i--)
                if(fa[a][i]&&dep[fa[a][i]]>=dep[b])
                    a=fa[a][i];
            if(a==b) return a;
            for(int i=18;i>=0;i--)
                if(fa[a][i]!=fa[b][i])
                    a=fa[a][i],b=fa[b][i];
            return fa[a][0];
        }
        int dis(int a,int b) {return dep[a]+dep[b]-2*dep[lca(a,b)];}
        void Insert(int v,int f) {
            fa[v][0]=f;
            for(int i=1;i<=18;i++) fa[v][i]=fa[fa[v][i-1]][i-1];
            dep[v]=dep[f]+1;
            int da=dis(A,v),db=dis(B,v);
            mxdis=max(mxdis,max(da,db));
            if(da==mxdis) B=v;
            else if(db==mxdis) A=v;
        }
    }
    
    int main() {
        int cas=Get();
        n=Get();
        for(int i=1;i<=n;i++) st[i].insert(0);
        A=B=1;
        for(int i=2;i<=n;i++) {
            int a=Get()^ans;
            DIS::Insert(i,a);
            Link(i,a);
            Make_root(A);
            access(B);
            Splay(B);
            cout<<(ans=DIS::mxdis+mx[B]-(mx[B]!=0))<<"\n";
        }
        return 0;
    }

转载于:https://www.cnblogs.com/hchhch233/p/10596130.html

[img]: /images/20211220/a7bf4b0cb78a4a4788b9721266f1dea4.png
[2016]: https://www.cnblogs.com/hchhch233/p/10566528.html