题面
松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在”树“上。
松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，......，最后到an，去参观新家。可是这样会导致维尼重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。
维尼是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。
因为松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。
2<= n <=300000
分析
很明显的树上点差分，但是直接标记不太对，因为会有既是起点又是终点的点被标记两次。
我们只需要将差分的子树和求出来后在ans里对2~n-1个点每个点减一，由于最后一个点是餐厅，所以也也减一。
代码
- #include<bits/stdc++.h>
- using namespace std;
- #define N 300030
- int n,cnt;
- int a[N],c[N],ans[N],dep[N],first[N],fa[N][20];
- struct email
- {
- int u,v;
- int nxt;
- }e[N*4];
- inline void add(int u,int v)
- {
- e[++cnt].nxt=first[u];first[u]=cnt;
- e[cnt].u=u;e[cnt].v=v;
- }
- template<class T>
- inline void read(T &x)
- {
- x=0;int f=1;static char c=getchar();
- while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
- while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}
- x*=f;
- }
- inline void pre(int u,int f)
- {
- for(int i=1;(1<<i)<=dep[u];i++)
- fa[u][i]=fa[fa[u][i-1]][i-1];
- for(int i=first[u];i;i=e[i].nxt)
- {
- int v=e[i].v;
- if(v==f)continue;
- dep[v]=dep[u]+1;
- fa[v][0]=u;
- pre(v,u);
- }
- }
- inline int lca(int x,int y)
- {
- if(dep[x]<dep[y])swap(x,y);
- int t=dep[x]-dep[y];
- for(int i=0;(1<<i)<=t;i++)
- if((1<<i)&t)
- x=fa[x][i];
- if(x==y)return x;
- for(int i=19;i>=0;i--)
- if(fa[x][i]!=fa[y][i])
- x=fa[x][i],y=fa[y][i];
- return fa[x][0];
- }
- inline void dfs(int u,int f)
- {
- for(int i=first[u];i;i=e[i].nxt)
- {
- int v=e[i].v;
- if(v==f)continue;
- dfs(v,u);
- c[u]+=c[v];
- }
- ans[u]=c[u];
- }
- int main()
- {
- read(n);
- for(int i=1;i<=n;i++)read(a[i]);
- for(int i=1;i<n;i++)
- {
- int u,v;
- read(u),read(v);
- add(u,v);add(v,u);
- }
- pre(1,0);
- for(int i=1;i<n;i++)
- {
- int u=a[i],v=a[i+1],LCA=lca(u,v);
- c[u]++,c[v]++,c[LCA]--,c[fa[LCA][0]]--;
- }
- dfs(1,0);
- for(int i=2;i<=n;i++)ans[a[i]]--;
- for(int i=1;i<=n;i++)printf("%d ",ans[i]);;
- return 0;
- }