思路
我们换一种求(dep[lca(i,j)])的方法。
将从根到(i)的路径上所有点的权值加(1)，然后求从根节点到j路径上点的权值和。就是(i)和(j)的(lca)的深度。
以此类推，对于求(sumlimits_{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
",(ask[i].ans - ask[i - 1].ans + mod) % mod);
return 0;
}