题目链接

思路

我们换一种求\(dep[lca(i,j)]\)的方法。
将从根到\(i\)的路径上所有点的权值加\(1\)，然后求从根节点到j路径上点的权值和。就是\(i\)和\(j\)的\(lca\)的深度。
以此类推，对于求\(\sum\limits_{i=l}^rdep[lca(i,z)]\)，我们可以对于从l到r中的每个节点到根节点的路径上的点权值加\(1\)，然后求一边从\(z\)到根节点路径和即可。这个可以用树链剖分做到。
然后再考虑多次询问。发现这个题可以离线。那就比较好处理了。
因为每次询问都是形如\([l,r]\)的形式。所以可以通过\([0,r]-[0,l-1]\)来得到\([l,r]\)的答案。所以我们对于询问离线之后，分别在每次询问的\(l-1\)和\(r\)处询问一次。相减就是答案。

代码

/*
* @Author: wxyww
* @Date:   2019-01-29 14:50:20
* @Last Modified time: 2019-01-29 16:13:25
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define int ll
const int N = 100010,mod = 201314;
vector<int>e[N];
ll read() {
    ll x=0,f=1;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();
    }
    return x*f;
}

int dep[N],top[N],son[N],dfn[N],siz[N],fa[N];
void dfs1(int u,int father) {
    fa[u] = father;dep[u] = dep[father] + 1;siz[u] = 1;
    int k = e[u].size();
    for(int i = 0;i < k;++i) {
        int v = e[u][i];
        if(v == father) continue;
        dfs1(v,u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}

int tot;
void dfs2(int u,int father,int tt) {
    dfn[u] = ++tot;top[u] = tt;
    int k = e[u].size();
    if(!son[u]) return;
    dfs2(son[u],u,tt);
    for(int i = 0;i < k;++i) {
        int v = e[u][i];
        if(v == father || v == son[u]) continue;
        dfs2(v,u,v);
    }
}

int tree[N << 2],lazy[N << 2];
void pushup(int rt) {
    tree[rt] = (tree[rt << 1] + tree[rt << 1 | 1]) % mod;
}

void pushdown(int rt,int ln,int rn) {
    if(lazy[rt]) {
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1] %= mod;
        lazy[rt << 1 | 1] += lazy[rt];
        lazy[rt << 1 | 1] %= mod;
        tree[rt << 1] += lazy[rt] * ln;
        tree[rt << 1] %= mod;
        tree[rt << 1 | 1] += lazy[rt] * rn;
        tree[rt << 1 | 1] %= mod;
        lazy[rt] = 0;
    }
}

void update(int rt,int l,int r,int L,int R,int c) {
    if(L <= l && R >= r) {
        lazy[rt] += c;
        lazy[rt] %= mod;
        tree[rt] += c * (r - l + 1);
        tree[rt] %= mod;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(rt,mid - l + 1,r - mid);
    if(L <= mid) update(rt << 1,l,mid,L,R,c);
    if(R > mid) update(rt << 1 | 1,mid + 1,r,L,R,c);
    pushup(rt);
}

int query(int rt,int l,int r,int L,int R) {
    if(L <= l && R >= r)
        return tree[rt];
    int mid = (l + r) >> 1;
    pushdown(rt,mid - l + 1,r - mid);
    int ans = 0;
    if(L <= mid) ans += query(rt << 1,l,mid,L,R),ans %= mod;
    if(R > mid) ans += query(rt << 1 | 1,mid + 1,r,L,R),ans %= mod;
    return ans;
}

void UPDATE(int rt,int c) {
    while(rt != 0) {
        update(1,1,tot,dfn[top[rt]],dfn[rt],c);
        rt = fa[top[rt]];
    }
}

int Query(int rt) {
    int ans = 0;
    while(rt != 0) {
        ans += query(1,1,tot,dfn[top[rt]],dfn[rt]);
        ans %= mod;
        rt = fa[top[rt]];
    }
    return ans;
}

struct node {
    int id,z,x,ans;
}ask[N];

bool cmp(node x,node y) {
    return x.x < y.x;
}

bool cmp2(node x,node y) {
    return x.id < y.id;
}
int js;
signed main() {
    int n = read(),Q = read();
    for(int i = 2;i <= n;++i) {
        int x = read() + 1;
        e[i].push_back(x);e[x].push_back(i);
    }
    for(int i = 1;i <= Q;++i) {
        int l = read() + 1,r = read() + 1,z = read() + 1;
        ask[++js].id = js;
        ask[js].x = l - 1;ask[js].z = z;
        ask[++js].id = js;
        ask[js].x = r;ask[js].z = z;
    }
    dfs1(1,0);
    dfs2(1,0,1);
    sort(ask + 1,ask + js + 1,cmp);
    int now = 1;
    while(ask[now].x == 0) ++now;
    for(int i = 1;i <= n;++i) {
        UPDATE(i,1);
        while(ask[now].x == i) {
            ask[now].ans = Query(ask[now].z);
            ++now;
        }
    }
    sort(ask + 1,ask + js + 1,cmp2);
    for(int i = 2;i <= js;i += 2) 
        printf("%lld\n",(ask[i].ans - ask[i - 1].ans + mod) % mod);
    return 0;
}