题目描述
松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在”树“上。
松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，......，最后到an，去参观新家。可是这样会导致维尼重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。
维尼是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。
因为松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。
输入输出格式
输入格式：
第一行一个整数n，表示房间个数第二行n个整数，依次描述a1-an接下来n-1行，每行两个整数x，y，表示标号x和y的两个房间之间有树枝相连。
输出格式：
一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。
输入输出样例
说明
2<= n <=300000
//记录从哪一个房间出发，update(出发点，终点,add) //因为从房间出发的时候不需要糖果，到达的时候才需要糖果 //所以update的时候会在出发点多放一块糖果 //那我们就update(s,s,-1),把多放的那块减去 //第一个房间是起点，提前在for循环外边放上一块糖。 //last记录起点是谁 //这样，在每次update之前都先把last上的糖--，然后update（区间） //最后让终点的糖--，因为题目中说最后一个点是餐厅，不用放糖 #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int N=3e5+5; int n; int a[N]; int head[N],num_edge; struct Edge { int v,nxt; }edge[N<<1]; struct NODE { int fa,son; int top,dep; int s,t; int size; }node[N]; struct TREE { TREE *lson,*rson; int l,r,mid,len; int sum,add; }tree[N<<2]; typedef TREE* Tree; Tree now_node=tree,Root; inline int read() { char c=getchar();int num=0; for(;!isdigit(c);c=getchar()); for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num; } inline void add_edge(int u,int v) { edge[++num_edge].v=v; edge[num_edge].nxt=head[u]; head[u]=num_edge; } void dfs1(int u) { node[u].size=1; for(int i=head[u],v;i;i=edge[i].nxt) { v=edge[i].v; if(v==node[u].fa) continue; node[v].fa=u; node[v].dep=node[u].dep+1; dfs1(v); node[u].size+=node[v].size; if(node[v].size>node[node[u].son].size) node[u].son=v; } } int bound; void dfs2(int u,int top) { node[u].top=top; node[u].s=++bound; if(node[u].son) { dfs2(node[u].son,top); for(int i=head[u],v;i;i=edge[i].nxt) { v=edge[i].v; if(v==node[u].son||v==node[u].fa) continue; dfs2(v,v); } } node[u].t=bound; } void build(Tree &root,int l,int r) { root=++now_node; root->l=l,root->r=r,root->mid=l+r>>1; root->len=r-l+1; if(l==r) return; build(root->lson,l,root->mid); build(root->rson,root->mid+1,r); } inline void pushdown(Tree root) { if(root->add) { root->lson->add+=root->add; root->rson->add+=root->add; root->lson->sum+=root->add*root->lson->len; root->rson->sum+=root->add*root->rson->len; root->add=0; } } void update(const Tree &root,int l,int r,int add) { if(root->l==l&&root->r==r) { root->sum+=root->len*add; root->add+=add; return; } pushdown(root); if(r<=root->mid) update(root->lson,l,r,add); else if(l>root->mid) update(root->rson,l,r,add); else { update(root->lson,l,root->mid,add); update(root->rson,root->mid+1,r,add); } // root->sum=root->lson->sum+=root->rson->sum; 不用pushup } int query(const Tree &root,int pos) { if(root->l==root->r) return root->sum; pushdown(root); if(pos<=root->mid) return query(root->lson,pos); else return query(root->rson,pos); } inline void Modify(int x,int y) { int fx=node[x].top,fy=node[y].top; while(fx!=fy) { if(node[fx].dep>node[fy].dep) { update(Root,node[fx].s,node[x].s,1); x=node[fx].fa; fx=node[x].top; } else { update(Root,node[fy].s,node[y].s,1); y=node[fy].fa; fy=node[y].top; } } if(node[x].dep>node[y].dep) update(Root,node[y].s,node[x].s,1); else update(Root,node[x].s,node[y].s,1); } int main() { n=read(); for(int i=1;i<=n;++i) a[i]=read(); for(int i=1,u,v;i<n;++i) { u=read(),v=read(); add_edge(u,v); add_edge(v,u); } dfs1(1); dfs2(1,1); build(Root,1,n); int last=a[1]; update(Root,node[last].s,node[last].s,1); //起点放糖 for(int i=2;i<=n;++i) { update(Root,node[last].s,node[last].s,-1); //让起点的糖-- Modify(last,a[i]); last=a[i]; } update(Root,node[last].s,node[last].s,-1); //终点的糖-- for(int i=1;i<=n;++i) //查询每个房间要放多少糖 printf("%d ",query(Root,node[i].s)); return 0; }