转化比较巧妙，考场上想傻逼了的题目。很好打。

Problem

给定一棵只有一个点的树，1e5次操作，每次加一个点后问至多交换一次两棵子树后的最大直径长度。强制在线。

Solution

考虑事实上就是把直径上的链剖出然后询问最长支链的长度 $lp$ ，答案就是 $d+max(lp-1, 0)$ 。

那么考虑每次加入一个点之后直径和最长支链的变化。如果直径变化，考虑另一条被换下来的支链一定是这条原支链的现长度-1。那么如果原支链的原长度就是最长支链，就直接考虑另一条被换下来的支链更新最长支链即可。如果不是最长支链，那么理论上最长支链是不会变化的，但是为了避免奇怪的错误我们还是要更新一下最长支链的点。

如果直径不变化，那么直接用新加的点更新最长支链即可。

倍增维护。

Code

// Code by ajcxsu
// Problem: forest

#include<bits/stdc++.h>
using namespace std;

template<typename T> inline void gn(T &x) {
    char ch=getchar(), pl=0; x=0;
    while(!isdigit(ch)) pl=(ch=='-'), ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}

const int N=2e5+10, OP=19;
int gup[OP][N], dep[N];
void add(int x, int fa) {
    gup[0][x]=fa, dep[x]=dep[fa]+1;
    for(int j=1; j<OP; j++)
        gup[j][x]=gup[j-1][gup[j-1][x]];
}
int lca(int s, int t) {
    if(dep[s]<dep[t]) swap(s, t);
    for(int j=OP-1; j>=0; j--) if(dep[gup[j][s]]>=dep[t]) s=gup[j][s];
    if(s==t) return s;
    for(int j=OP-1; j>=0; j--)
        if(gup[j][s]!=gup[j][t]) s=gup[j][s], t=gup[j][t];
    return gup[0][s];
}
int dis(int s, int t) {
    return dep[s]+dep[t]-2*dep[lca(s, t)];
}
int u=1, v=1, p=1, fa, len, lp, lst;
int cac(int x) { return dis(x, u)+dis(x, v)-len>>1; }

int main() {
    #ifndef LOCAL
    freopen("forest.in","r",stdin);
    freopen("forest.out","w",stdout);
    #endif
    dep[1]=1;
    int n, tod;
    gn(n), gn(n);
    int tmp;
    for(int i=2; i<=n; i++) {
        gn(fa), fa^=lst;
        add(i, fa);
        int la=dis(u, i), lb=dis(v, i);
        if(la>len || lb>len) {
            if(la>lb)
                tod=v, v=i, len=la;
            else
                tod=u, u=i, len=lb;
            if((tmp=cac(tod))>lp) 
                lp=tmp, p=tod;
        }
        else if(((la+lb-len)>>1)>lp)
            lp=(la+lb-len)>>1, p=i;
        printf("%d\n", lst=len+max(lp-1, 0));
    }
    return 0;
}