https://www.cnblogs.com/Gloid/p/9412357.html差分一下是一样的问题。感觉几年没写过树剖了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 50010
#define P 998244353
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int 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<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,q,k,fa[N],p[N],w[N],ans[N],t;
int dfn[N],id[N],size[N],deep[N],top[N],son[N],cnt;
int tree[N<<2],lazy[N<<2],L[N<<2],R[N<<2],s[N<<2];
struct data{int to,nxt;
}edge[N];
struct data2
{
int x,y,i;
bool operator <(const data2&a) const
{
return x<a.x;
}
}Q[N];
void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
int ksm(int a,int k)
{
int s=1;
for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;
return s;
}
void dfs1(int k)
{
size[k]=1;
for (int i=p[k];i;i=edge[i].nxt)
{
deep[edge[i].to]=deep[k]+1;
dfs1(edge[i].to);
size[k]+=size[edge[i].to];
if (size[edge[i].to]>size[son[k]]) son[k]=edge[i].to;
}
}
void dfs2(int k,int from)
{
dfn[k]=++cnt;id[cnt]=k;top[k]=from;
if (son[k]) dfs2(son[k],from);
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=son[k]) dfs2(edge[i].to,edge[i].to);
}
void build(int k,int l,int r)
{
L[k]=l,R[k]=r;
if (l==r) {s[k]=w[deep[id[l]]];return;}
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
s[k]=(s[k<<1]+s[k<<1|1])%P;
}
void update(int k,int x)
{
lazy[k]+=x;
tree[k]=(tree[k]+1ll*x*s[k])%P;
}
void down(int k)
{
update(k<<1,lazy[k]);
update(k<<1|1,lazy[k]);
lazy[k]=0;
}
void add(int k,int l,int r)
{
if (L[k]==l&&R[k]==r) {update(k,1);return;}
if (lazy[k]) down(k);
int mid=L[k]+R[k]>>1;
if (r<=mid) add(k<<1,l,r);
else if (l>mid) add(k<<1|1,l,r);
else add(k<<1,l,mid),add(k<<1|1,mid+1,r);
tree[k]=(tree[k<<1]+tree[k<<1|1])%P;
}
int query(int k,int l,int r)
{
if (L[k]==l&&R[k]==r) return tree[k];
if (lazy[k]) down(k);
int mid=L[k]+R[k]>>1;
if (r<=mid) return query(k<<1,l,r);
else if (l>mid) return query(k<<1|1,l,r);
else return (query(k<<1,l,mid)+query(k<<1|1,mid+1,r))%P;
}
void ins(int x)
{
while (x)
{
add(1,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
}
int get(int x)
{
int s=0;
while (x)
{
s=(s+query(1,dfn[top[x]],dfn[x]))%P;
x=fa[top[x]];
}
return s;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj5507.in","r",stdin);
freopen("bzoj5507.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read(),q=read(),k=read();
for (int i=2;i<=n;i++)
{
fa[i]=read();
addedge(fa[i],i);
}
for (int i=0;i<=n;i++) w[i]=ksm(i,k);
for (int i=n;i>=1;i--) w[i]=(w[i]-w[i-1]+P)%P;
deep[1]=1;dfs1(1);dfs2(1,1);
build(1,1,n);
for (int i=1;i<=q;i++) Q[i].x=read(),Q[i].y=read(),Q[i].i=i;
sort(Q+1,Q+q+1);
int cur=0;
for (int i=1;i<=q;i++)
{
while (cur<Q[i].x) ins(++cur);
ans[Q[i].i]=get(Q[i].y);
}
for (int i=1;i<=q;i++) printf("%d\n",ans[i]);
return 0;
}