#include<cstdio>
#include<iostream>


struct node{
	 int to,nxt;
}e[MAXN<<2];

void addedge(int u,int v){
   e[++tot].to=v;
   nxt[tot]=head[u];
   head[u]=tot;
}

inline void updatetree(int s,int t){
	while(top[s]!=top[t]){
		if (dep[s]>dep[t]) mswap(s,t);
		update(id[top[t]],id[t],c,1,n,1);
		t=fa[top[t]];
	}
	if (dep[s]>dep[t]) mswap(s,t);
	update(id[s],id[t],1,n,1);
}

inline void getanstree(int s,int t){
	int ans=0;
	while (top[s]!=top[t]){
	   if (dep[s]>dep[t]) mswap(s,t);
	   update(id[top[t]],id[t],1,n,1);
	   t=fa[top[t]]; 
	}
	if (dep[s]>dep[t]) mswap(s,t);
	ans+=getans(id[s],id[t],1,n,1);
	return ans;
}

inline void updateson(int x,int c){
	update(id[x],id[x]+siz[x]-1,c,1,n,1);
}
inline int getansson(int x){
	return getans(id[x],id[x]+siz[x]-1,1,n,1);
}
void dfs1(int x,int fath,int deep){
	siz[x]=1;
	fa[x]=fath;
	dep[x]=deep;
	maxson=-1;
	for (int i=head[x];i;i=e[i].nxt){
	   int v=e[i].to;
	   if (v==x) continue;
	   dfs1(v,x,deep+1);
	   siz[x]+=siz[v];
	   if (siz[v]>maxson)
	     { 
	        siz[v]=maxson;
	        son[x]=v;
		 } 
	}
}

void dfs2(int x,int fst){
	top[x]=fst;
	id[x]=++lim;
	w[id[x]]=a[x];
	if (!son[x]) return;
	dfs2(son[x],fst);
	for (register int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		if (v==fa[x]||v==son[x]) continue;
		dfs2(v,v);
	}
}