如题，不知道 UKE 时操作不合法还是什么问题。

另外下面的 56 分代码求调，主要问题是有几个点 UKE 一个点 WA 前面一些点 TLE

思路是 Top tree 上 dp

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+114;
struct node{
	int u,v,sz,id;//簇内答案（不包括界点） 到界定的距离最大的白点的距离
	char type;
	//u 在上面 v 在下面
}cluster[maxn];
namespace IO{
    const int SIZE=1<<21;
    static char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=oS+SIZE-1;
    int qr;
    char qu[55],c;
    bool f;
    #define getchar() (IO::iS==IO::iT?(IO::iT=(IO::iS=IO::ibuf)+fread(IO::ibuf,1,IO::SIZE,stdin),(IO::iS==IO::iT?EOF:*IO::iS++)):*IO::iS++)
    #define putchar(x) *IO::oS++=x,IO::oS==IO::oT?flush():0
    #define flush() fwrite(IO::obuf,1,IO::oS-IO::obuf,stdout),IO::oS=IO::obuf
    #define puts(x) IO::Puts(x)
    template<typename T>
    inline void read(T&x){
        for(f=1,c=getchar();c<48||c>57;c=getchar())f^=c=='-';
        for(x=0;c<=57&&c>=48;c=getchar()) x=(x<<1)+(x<<3)+(c&15);
        x=f?x:-x;
    }
    template<typename T>
    inline void write(T x){
        if(!x) putchar(48); if(x<0) putchar('-'),x=-x;
        while(x) qu[++qr]=x%10^48,x/=10;
        while(qr) putchar(qu[qr--]);
    }
    inline void Puts(const char*s){
        for(int i=0;s[i];++i)
            putchar(s[i]);
        putchar('\n');
    }
    struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}
using IO::read;
using IO::write;
int n;
int fa[maxn],ls[maxn],rs[maxn],d[maxn];
int root=1;//根簇
void compress(node x,node y,node &w){
	//x 在上面 y 在下面
	w.u=x.u,w.v=y.v;
	w.sz=x.sz+y.sz+1;
	fa[x.id]=fa[y.id]=w.id;
	ls[w.id]=x.id;
	rs[w.id]=y.id;
	w.type='C';
	root=w.id;
}
void rake(node x,node y,node &w){
	//把 x rake 到 y 上
	w.u=y.u,w.v=y.v;
	w.sz=x.sz+y.sz+1;
	fa[x.id]=fa[y.id]=w.id;
	ls[w.id]=x.id;
	rs[w.id]=y.id;
	w.type='R';
	root=w.id;
}
vector<int> E[maxn],e[maxn];
int father_pos[maxn];//一个点到其父亲的边的簇编号
int father[maxn];
int son[maxn],sz[maxn],tot;
vector<int> st[maxn];//重链上的点存到链顶
void dfs1(int u){
	sz[u]=1;
	for(int v:E[u]){
		if(v==father[u]) continue;
		father[v]=u;
		father_pos[v]=++tot;
		cluster[tot].u=u,cluster[tot].v=v,cluster[tot].id=tot;
		dfs1(v);
		if(sz[v]>sz[son[u]]) son[u]=v;
		sz[u]+=sz[v];
	}
}
void dfs2(int u,int tp){
	st[tp].push_back(u);
	if(son[u]!=0) dfs2(son[u],tp);
	for(int v:E[u]){
		if(v==father[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
//需要虚拟节点 n+1 作为根 只在第一次 dfs 以及最后根簇时调用
vector<int> vec[maxn];
vector<int> pre[maxn];
int solve(int l,int r,int u){
    if(l>r) return 0;
	if(l==r) return father_pos[vec[u][l]];
	int L=l,R=r;
	while(L+1<R){
		int mid=(L+R)>>1;
		if((pre[u][mid]-pre[u][l-1])*2<=(pre[u][r]-pre[u][l-1])) L=mid;
		else R=mid;
	}
	int mid=L;
	int lson=solve(l,mid,u);
	int rson=solve(mid+1,r,u);
	int res=++tot;
	cluster[tot].id=tot;
	rake(cluster[lson],cluster[rson],cluster[res]);
	return res;
}
int calc(int l,int r,int u){
    if(l>r) return 0;
    if(l==r) return father_pos[vec[u][l]];
	int L=l,R=r;
	while(L+1<R){
		int mid=(L+R)>>1;
		if((pre[u][mid]-pre[u][l-1])*2<=(pre[u][r]-pre[u][l-1])) L=mid;
		else R=mid;
	}
	int mid=L;
	int lson=calc(l,mid,u);
	int rson=calc(mid+1,r,u);
	int res=++tot;
    cluster[tot].id=tot;
	compress(cluster[lson],cluster[rson],cluster[res]);
	return res;
}
void dfs3(int u){
	for(int x:st[u]){
        if(son[x]==0) continue;
		pre[x].push_back(0);
		vec[x].push_back(0);
		for(int v:E[x]){
			if(v!=son[x]&&v!=father[x]){
				dfs3(v);
				//收缩 (x,v) 一个簇
				vec[x].push_back(v);
			}
		}
		//在对这些轻儿子簇按中点分治的方法合并起来
		for(int i=1;i<=vec[x].size()-1;i++){
			pre[x].push_back(pre[x][i-1]+sz[vec[x][i]]);
		}
		int rt=solve(1,vec[x].size()-1,x);
		if(rt!=0){
		    tot++;
		    cluster[tot].id=tot;
            rake(cluster[rt],cluster[father_pos[son[x]]],cluster[tot]);
            father_pos[son[x]]=tot;//rake 到重链上
		}
	}
	vec[u].clear();
	pre[u].clear();
	pre[u].push_back(0);
	vec[u].push_back(0);
	for(int x:st[u]){
		vec[u].push_back(x);
	}
	for(int i=1;i<=vec[u].size()-1;i++){
		pre[u].push_back(pre[u][i-1]+sz[vec[u][i]]-sz[son[vec[u][i]]]);
	}
	if(u!=1) father_pos[u]=calc(1,vec[u].size()-1,u);//把重链上的边 compress 成一条
	else father_pos[u]=calc(2,vec[u].size()-1,u);
	E[u].clear();
	if(u!=1) E[u].push_back(father[u]);
	return ;
}
int L[maxn],R[maxn],dfncnt,dfn[maxn];
int g[maxn];
void dfs(int u){
    if(u==0) return ;
    L[u]=++dfncnt;
    if(cluster[u].type!='R') g[u]=1;
    dfs(ls[u]);
    if(cluster[u].type!='R') g[u]|=g[ls[u]];
    dfs(rs[u]);
    g[u]|=g[rs[u]];
    if(ls[u]!=0) dfn[cluster[ls[u]].v]=++dfncnt;
    R[u]=dfncnt;
}
void add(int u,int stop,int P){
	for(int v:e[u]){
		if(v!=stop&&L[P]<=dfn[v]&&dfn[v]<=R[P]){
            putchar('+');
            write(v);
			add(v,stop,P);
		}
	}
}//加入一个簇的信息
int f[maxn];
void solve(int u);
void DP1(int u);
void DP2(int u);
void solve(int u){
    //先处理除了 rake 节点左儿子以外其他点
    DP1(u);
    DP2(u);
}
void DP1(int u){
    if(ls[u]==0&&rs[u]==0){
        if(d[cluster[u].v]==1){
            putchar('+');
            write(cluster[u].u);
            putchar('=');
            write(cluster[u].v);
            putchar('-');
        }
        return ;
    }
    if(cluster[u].type=='C'){
        DP1(ls[u]);
        f[u]|=f[ls[u]];
        add(cluster[ls[u]].u,cluster[ls[u]].v,ls[u]);
        putchar('+');
        write(cluster[ls[u]].u);
        putchar('=');
        write(cluster[ls[u]].v);
        DP1(rs[u]);
        f[u]|=f[rs[u]];
        putchar('-');
        for(int i=1;i<=cluster[ls[u]].sz;i++) putchar('-');
    }else{
        if(g[rs[u]]==0) return ;
        add(cluster[ls[u]].u,cluster[ls[u]].v,ls[u]);
        putchar('+');
        write(cluster[ls[u]].v);
        DP1(rs[u]);
        f[u]|=f[ls[u]];
        putchar('-');
        for(int i=1;i<=cluster[ls[u]].sz;i++) putchar('-');
        //左儿子先不处理
        f[u]=1;
    }
}
void DP2(int u){
    if(ls[u]==0&&rs[u]==0) return ;
    if(cluster[u].type=='C'){
        if(f[ls[u]]==1){
            putchar('+');
            write(cluster[u].v);
            add(cluster[rs[u]].u,cluster[rs[u]].v,rs[u]);
            DP2(ls[u]);
            for(int i=1;i<=cluster[rs[u]].sz;i++) putchar('-');
            putchar('-');
        }
        if(f[rs[u]]==1){
            putchar('+');
            write(cluster[u].u);
            add(cluster[ls[u]].u,cluster[ls[u]].v,ls[u]);
            DP2(rs[u]);
            for(int i=1;i<=cluster[ls[u]].sz;i++) putchar('-');
            putchar('-');
        }

    }else{
        if(f[rs[u]]==1){
            putchar('+');
            write(cluster[ls[u]].v);
            add(cluster[ls[u]].u,cluster[ls[u]].v,ls[u]);
            DP2(rs[u]);
            for(int i=1;i<=cluster[ls[u]].sz;i++) putchar('-');
            putchar('-');
        }
        putchar('+');
        write(cluster[rs[u]].v);
        add(cluster[rs[u]].u,cluster[rs[u]].v,rs[u]);
        solve(ls[u]);//这时候再处理左儿子
        for(int i=1;i<=cluster[rs[u]].sz;i++) putchar('-');
        putchar('-');
    }
}
void work(){
    root=1;
    tot=0;
    dfncnt=0;
    for(int i=0;i<maxn;i++){
        cluster[i].type=cluster[i].u=cluster[i].v=cluster[i].id=cluster[i].sz=0;
        ls[i]=rs[i]=fa[i]=0;
        d[i]=0;
        f[i]=g[i]=0;
        E[i].clear();
        e[i].clear();
        father[i]=father_pos[i]=son[i]=sz[i]=0;
        L[i]=R[i]=dfn[i]=0;
        st[i].clear();
        vec[i].clear();
        pre[i].clear();
    }
    for(int i=2;i<=n;i++){
        cin>>father[i];
        E[i].push_back(father[i]);
        E[father[i]].push_back(i);
        e[father[i]].push_back(i);
        d[i]++;
        d[father[i]]++;
    }
    dfs1(1);
    dfs2(1,1);
    dfs3(1);
    dfs(root);
    putchar('=');
    write(cluster[root].u);
    solve(root);
    putchar('!');
    putchar('\n');
    return ;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while(cin>>n) work();
    return 0;
}