给出一棵树和q个询问,每个询问给出一个区间[l,r]和一个数z,对于每个询问,求

\sum_{i=l}^{r}dep[LCA(i,z)]

链接

LOJ

题解

首先把询问拆分成[1,l-1]和[1,r]分别计算贡献.在计算LCA的深度时,有一个技巧是把其中一个点到根节点的路径上的所有点的点权加1,然后查询另一个点到根节点的点权之和.正确性是显然的.

对于这个问题先把所有的询问离线处理.从0开始依次把其到根节点的点权加1,然后当检测到此时枚举到的点的标号是某个询问的右端点时,就更新一次答案.

点权的修改和查询基于线段树和树剖实现.总的时间复杂度为

O(nlognlogn)

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 50010
#define MOD 201314
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,i,q,root,x,l,r,tot,s;
int Ans[N],fa[N],hson[N],w[N],top[N],size[N];

vector <int> son[N];

struct Data{
    int r,p,f,z;
}a[N*2];

struct Tree{
    int l,r,cl;
    LL d,lz;
}t[N*8];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline bool cmp(const Data &x,const Data &y){return x.r<y.r;}

inline void Maketree(int x,int low,int high){
    int mid=(low+high)>>1;
    t[x].l=low; t[x].r=high;
    if (low==high)  return;
    Maketree(l(x),low,mid); Maketree(r(x),mid+1,high);
}

inline void Push(int x){
    int p=t[x].lz;
    t[l(x)].d=(t[l(x)].d+p*(t[l(x)].r-t[l(x)].l+1))%MOD;
    t[r(x)].d=(t[r(x)].d+p*(t[r(x)].r-t[r(x)].l+1))%MOD;
    t[l(x)].lz+=p;  t[r(x)].lz+=p;  t[x].lz=0;
}

inline void Add(int x,int low,int high){
    int mid=(t[x].l+t[x].r)>>1;
    if (t[x].lz)    Push(x);
    if (low==t[x].l&&high==t[x].r)  {t[x].d=(t[x].d+t[x].r-t[x].l+1)%MOD;   t[x].lz++;  return;}
    if (high<=mid)  Add(l(x),low,high);
    else if (low>mid)   Add(r(x),low,high);
    else Add(l(x),low,mid),Add(r(x),mid+1,high);
    t[x].d=t[l(x)].d+t[r(x)].d;
}

inline int Query(int x,int low,int high){
    int mid=(t[x].l+t[x].r)>>1;
    if (t[x].lz)    Push(x);
    if (low==t[x].l&&high==t[x].r)  return t[x].d;
    if (high<=mid)  return Query(l(x),low,high);
    else if (low>mid)   return Query(r(x),low,high);
    else return (Query(l(x),low,mid)+Query(r(x),mid+1,high))%MOD;
}

inline void Dfs(int x){
    size[x]=1;
    if (!son[x].size()) return;
    for (auto i : son[x]){
        Dfs(i); size[x]+=size[i];
        if (size[i]>size[hson[x]])  hson[x]=i;
    }
}

inline void Cut(int x){
    w[x]=++s;
    if (!son[x].size()) return;
    top[hson[x]]=top[x];    Cut(hson[x]);
    for (auto i : son[x]){
        if (i==hson[x]) continue;
        top[i]=i;   Cut(i);
    }
}

inline void Work(){
    int i=0,j=1,x=0,sum=0;
    for (i=1;i<=n;i++){
        x=i;
        while (x){
            Add(1,w[top[x]],w[x]);  x=fa[top[x]];
        }
        while (a[j].r==i){
            sum=0;  x=a[j].z;
            while (x){
                sum=(sum+Query(1,w[top[x]],w[x]))%MOD;  x=fa[top[x]];
            }
            Ans[a[j].p]=(Ans[a[j].p]+sum*a[j].f+MOD)%MOD;
            j++;
        }
        if (j>tot)  break;
    }
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();   q=read();
    for (i=2;i<=n;i++){
        x=read();   x++;
        fa[i]=x;    son[x].push_back(i);
    }
    for (i=1;i<=q;i++){
        l=read()+1; r=read()+1; x=read()+1;
        a[++tot].r=r;   a[tot].f=1; a[tot].p=i; a[tot].z=x;
        if (l>1){
            a[++tot].r=l-1; a[tot].f=-1;
            a[tot].p=i; a[tot].z=x;
        }
    }
    sort(a+1,a+1+tot,cmp);
    Dfs(1); top[1]=1;   Cut(1);
    Maketree(1,1,n);    Work();
    for (i=1;i<=q;i++)  printf("%d\n",Ans[i]);
    return 0;
}