#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);
}
}