Description

给出一个n个节点的有根树（编号为0到n-1，根节点为0）。

一个点的深度定义为这个节点到根的距离+1。

设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。

有q次询问，每次询问给出l r z，求∑l≤i≤rdep[LCA(i,z)] 。

（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）

Solution

首先把询问拆成两个部分

可以把每个点的贡献看成是它到根节点路径上的累加

所以每次加点的时候，就把它到根的路径上全部+1

按顺序加点，询问时直接对它到根的路径求和就可以了

Code 

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 50005struct edge{int to,nex;}e[MN];int en,hr[MN];inline void ins(int f,int t){e[++en]=(edge){t,hr[f]};hr[f]=en;}int fa[MN],dep[MN],mx[MN],siz[MN],top[MN],dfn[MN],dind;void dfs1(int x=1){    dep[x]=dep[fa[x]]+(siz[x]=1);register int i;    for(i=hr[x];i;i=e[i].nex) dfs1(e[i].to),siz[x]+=siz[e[i].to],siz[e[i].to]>siz[mx[x]]?mx[x]=e[i].to:0;}void dfs2(int x=1,int tp=1){    top[x]=tp;dfn[x]=++dind;if(mx[x]) dfs2(mx[x],tp); register int i;    for(i=hr[x];i;i=e[i].nex) if(mx[x]^e[i].to) dfs2(e[i].to,e[i].to);}class BIT{    #define NM 50005    #define reg register    #define lb(x) (x&(-x))    private:        ll t1[NM],t2[NM],N;    public:        BIT(int _n):N(_n){memset(t1,0,sizeof t1);memset(t2,0,sizeof t2);}        inline void CC(int p,int v){for(reg int x=p;x<=N;x+=lb(x))t1[x]+=v,t2[x]+=v*p*1ll;}        inline void C(int l,int r,int x){CC(l,x);CC(r+1,-x);}        inline ll GG(int p){ll r=0;for(reg int x=p;x;x-=lb(x))r+=(p+1)*t1[x]-t2[x];return r;}        inline ll G(int l,int r){return GG(r)-GG(l-1);}    #undef NM    #undef lb    #undef reg};struct ques{    int z,id,a,val;    bool operator<(const ques&o) const{return z
     
      <<1];int n,Q,ans[MN];inline int INS_Query(int x,bool p){    static BIT T(n);    if(p)    {        while(x)        {            T.C(dfn[top[x]],dfn[x],1);            x=fa[top[x]];        }        return 0;    }    else    {        int r=0;        while(x)        {            r+=T.G(dfn[top[x]],dfn[x]);            x=fa[top[x]];        }        return r;    }}int main(){//  freopen("tree.in","r",stdin);//  freopen("tree.out","w",stdout);    n=read();Q=read();    register int i,pos;    for(i=2;i<=n;++i) fa[i]=read()+1,ins(fa[i],i);    for(i=1;i<=Q;++i)    {        q[i*2-1].z=read(),q[i*2].z=read()+1;        q[i*2-1].a=q[i*2].a=read()+1;        q[i*2].id=q[i*2-1].id=i;        q[i*2].val=1;q[i*2-1].val=-1;    }    std::sort(q+1,q+Q*2+1);dfs1();dfs2();    for(pos=0,i=1;i<=Q*2;++i)    {        for(;pos
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！