Time Limit: 10 Sec Memory Limit: 128 MB Submit: 3084 Solved: 1681
松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，……，最后到an，去参观新家。
可是这样会导致维尼重复走很多房间，懒惰的维尼不听地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。维尼是个馋家伙，立马就答应了。
现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。因为松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。
第一行一个整数n，表示房间个数
第二行n个整数，依次描述a1-an
接下来n-1行，每行两个整数x，y，表示标号x和y的两个房间之间有树枝相连。
一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。
5 1 4 5 3 2 1 2 2 4 2 3 4 5
1 2 1 2 1
2<= n <=300000
解析：
树上差分（当然硬上树链剖分也是没问题的。。。）。
简化题目后发现只需要维护 u 到 v 路径上点权加一以及求点权，那么就可以用差分的方法解决。
对于 u 到 v 路径上点权加一的操作，只需要在 u 和 v 打一个加一标记，在LCA[u,v] 和 fa[LCA(u,v)] 打一个减一标记，这样一个点的子树的和即为这个点的实际值。
感性理解一下就是在LCA[u,v]减一是为了避免重复算，在fa[LCA(u,v)] 打一个减一标记是为了防止对LCA(u,v)上面产生影响。
代码：
#include <bits/stdc++.h> using namespace std; const int Max=300005; int n,m,s; int first[Max],sum[Max],a[Max],top[Max],fa[Max],dep[Max],son[Max],size[Max]; struct shu{int to,next;}edge[Max<<1]; inline int get_int() { int x=0,f=1;char c; for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar()); if(c=='-') f=-1,c=getchar(); for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0'; return x*f; } inline void print(int x) { if(x>9) print(x/10); putchar('0'+x%10); } inline void build(int x,int y){edge[++s].next=first[x],first[x]=s,edge[s].to=y;} inline void dfs1(int p) { size[p]=1; for(int u=first[p];u;u=edge[u].next) { int to=edge[u].to; if(to==fa[p]) continue; fa[to]=p,dep[to]=dep[p]+1,dfs1(to),size[p]+=size[to]; if(size[to]>size[son[p]]) son[p]=to; } } inline void dfs2(int p,int tp) { top[p]=tp; if(!son[p]) return; dfs2(son[p],tp); for(int u=first[p];u;u=edge[u].next) { int to=edge[u].to; if(to==fa[p]||to==son[p]) continue; dfs2(to,to); } } inline void dfs3(int p) { for(int u=first[p];u;u=edge[u].next) { int to=edge[u].to; if(to==fa[p]) continue; dfs3(to); sum[p]+=sum[to]; } } inline int LCA(int x,int y) { while(top[x]^top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); x=fa[top[x]]; } return dep[x]<dep[y]?x:y; } inline void init() { n=get_int(); for(int i=1;i<=n;i++) a[i]=get_int(); for(int i=1;i<n;i++) { int x=get_int(),y=get_int(); build(x,y),build(y,x); } } inline void solve() { dfs1(1),dfs2(1,1); for(int i=1;i<n;i++) { int father=LCA(a[i],a[i+1]); sum[a[i]]++,sum[a[i+1]]++,sum[father]--,sum[fa[father]]--; } dfs3(1); for(int i=2;i<=n;i++) sum[a[i]]--; for(int i=1;i<=n;i++) print(sum[i]),putchar('\n'); } int main() { init(); solve(); return 0; }
