题意

树上操作

• $u$到$v$的路径上权值$+1$
• 询问每个点的权值

数据范围：$2 \le n \le 300000$

题解

树剖裸题
注意每次的终点作为下次的起点，会多$+1$，记得$-1$；最后一次也是，题目有特殊要求

代码：

#include<iostream>
#include<cstdio>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
const int N=300000+10;
int n,u,v;
int a[N];
int cnt,tot;
int head[N],siz[N],fa[N],son[N],dep[N],top[N],id[N];
struct edge{
    int nxt,to;
} e[N<<1];
struct node{
    int w,tag;
    inline node():w(0),tag(0){}
} T[N<<2];
inline void add(int u,int v){
    e[++cnt]=edge{head[u],v};
    head[u]=cnt;
}
void dfs1(int u){
    siz[u]=1;
    dep[u]=dep[fa[u]]+1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa[u])
            continue;
        fa[v]=u;
        dfs1(v);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v])
            son[u]=v;
    }
}
void dfs2(int u,int t){
    top[u]=t;
    id[u]=++tot;
    if(!son[u])
        return ;
    dfs2(son[u],t);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa[u] || v==son[u])
            continue;
        dfs2(v,v);
    }
}
inline void pushUp(int rt){
    T[rt].w=T[ls].w+T[rs].w;
}
inline void pushDown(int rt,int len){
    T[ls].w+=T[rt].tag*(len-(len>>1));
    T[rs].w+=T[rt].tag*(len>>1);
    T[ls].tag+=T[rt].tag;
    T[rs].tag+=T[rt].tag;
    T[rt].tag=0;
}
void update(int rt,int l,int r,int L,int R,int k){
    if(l>=L && r<=R){
        T[rt].w+=k*(r-l+1);
        T[rt].tag+=k;
        return ;
    }
    if(T[rt].tag!=0)
        pushDown(rt,r-l+1);
    int mid=l+r>>1;
    if(L<=mid)
        update(ls,l,mid,L,R,k);
    if(R>mid)
        update(rs,mid+1,r,L,R,k);
    pushUp(rt);
}
int query(int rt,int l,int r,int L,int R){
    if(l>=L && r<=R){
        return T[rt].w;
    }
    if(T[rt].tag!=0)
        pushDown(rt,r-l+1);
    int res=0;
    int mid=l+r>>1;
    if(L<=mid)
        res+=query(ls,l,mid,L,R);
    if(R>mid)
        res+=query(rs,mid+1,r,L,R);
    pushUp(rt);
    return res;
}
inline void Tupdate(int x,int y){
    for(;top[x]!=top[y];){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        update(1,1,tot,id[top[x]],id[x],1);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    update(1,1,tot,id[x],id[y],1);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs1(1);
    dfs2(1,1);
    for(int i=1;i<n;i++){
        Tupdate(a[i],a[i+1]);
        update(1,1,tot,id[a[i+1]],id[a[i+1]],-1);
    }
    for(int i=1;i<=n;i++)
        printf("%d\n",query(1,1,tot,id[i],id[i]));
    return 0;
}