洛谷 3285 [JLOI2014]松鼠的新家

【题解】

　　给出一条路径，问树上的点被经过了几次。

　　显然树剖之后树上差分就好了。

 #include<cstdio>
 #include<algorithm>
 #define N 300010
 #define rg register
 using namespace std;
 int n,tot,last[N],dep[N],fa[N],size[N],son[N],val[N],top[N],a[N];
 struct edge{
     int to,pre;
 }e[N<<];
 inline int read(){
     int k=,f=; char c=getchar();
     while(c<''||c>'')c=='-'&&(f=-),c=getchar();
     while(''<=c&&c<='')k=k*+c-'',c=getchar();
     return k*f;
 }
 void dfs1(int x){
     size[x]=; dep[x]=dep[fa[x]]+;
     for(rg int i=last[x],to;i;i=e[i].pre) if((to=e[i].to)!=fa[x]){
         fa[to]=x; dfs1(to);
         size[x]+=size[to];
         if(size[to]>size[son[x]]) son[x]=to;
     }
 }
 void dfs2(int x,int tp){
     top[x]=tp;
     if(son[x]) dfs2(son[x],tp);
     for(rg int i=last[x],to;i;i=e[i].pre)
         if((to=e[i].to)!=son[x]&&to!=fa[x]) dfs2(to,to);
 }
 inline int lca(int x,int y){
     int f1=top[x],f2=top[y];
     while(f1!=f2){
         if(dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
         x=fa[f1]; f1=top[x];
     }
     return dep[x]<dep[y]?x:y;
 }
 void dfs(int x){
     for(rg int i=last[x],to;i;i=e[i].pre) if((to=e[i].to)!=fa[x]){
         dfs(to);
         val[x]+=val[to];
     }
 }
 int main(){
     n=read();
     for(rg int i=;i<=n;i++) a[i]=read();
     for(rg int i=;i<n;i++){
         int u=read(),v=read();
         e[++tot]=(edge){v,last[u]}; last[u]=tot;
         e[++tot]=(edge){u,last[v]}; last[v]=tot;
     }
     dfs1();
     dfs2(,);
     for(rg int i=;i<=n;i++){
         int L=lca(a[i],a[i-]);
         val[a[i]]++; val[a[i-]]++; val[L]--; val[fa[L]]--;
         //printf("lca=%d\n",L);
     }
     dfs();
     for(rg int i=;i<=n;i++) val[a[i]]--;
     for(rg int i=;i<=n;i++) printf("%d\n",val[i]);
     return ;
 }