用的是 树链剖分&线段树 加delta=dep^k-(dep-1)^k

样例过了，测试点只过了 #9，#10

QAQ

#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
struct edge
{
	long long v,nxt;
}e[100005];
struct stree
{
	long long l,r,val,tag,dval;
}t[200005];
struct quest
{
	long long x,pos,id;
	bool operator<(const quest &t)const
	{
		return x<t.x;
	}
}q[50005];
long long n,Q,k,u,pos,cnt,cur;
long long head[50005],d[50005],ans[50005];
long long dep[50005],siz[50005],fa[50005],son[50005];
long long dfn[50005],p[50005],top[50005];
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1)
			res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
void addedge(int u,int v)
{
	e[++pos]={v,head[u]};
	head[u]=pos;
}
void dfs1(int u,int f)
{
	dep[u]=dep[f]+1;
	siz[u]=1;
	fa[u]=f;
	int maxson=0;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==f)
			continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>maxson)
		{
			maxson=siz[v];
			son[u]=v;
		}
	}
}
void dfs2(int u,int t)
{
	dfn[u]=++cnt;
	p[cnt]=u;
	top[u]=t;
	if(!son[u])
		return;
	dfs2(son[u],t);
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa[u]||v==son[u])
			continue;
		dfs2(v,v);
	}
}
void pushup(int idx)
{
	t[idx].val=(t[2*idx].val+t[2*idx+1].val)%mod;
	t[idx].dval=(t[2*idx].dval+t[2*idx+1].dval)%mod;
}
void add(int idx,long long val)
{
	t[idx].val=(t[idx].val+val*t[idx].dval)%mod;
	t[idx].tag=(t[idx].tag+val)%mod;
}
void pushdown(int idx)
{
	if(t[idx].tag)
	{
		add(2*idx,t[idx].tag);
		add(2*idx+1,t[idx].tag);
		t[idx].tag=0;
	}
}
void build(int idx,int l,int r)
{
	t[idx].l=l,t[idx].r=r;
	if(l==r)
	{
		t[idx].dval=d[dep[p[l]]];
		return;
	}
	int mid=l+r>>1;
	build(2*idx,l,mid);
	build(2*idx+1,mid+1,r);
	pushup(idx);
}
void update(int idx,int l,int r)
{
	if(t[idx].r<l||t[idx].l>r)
		return;
	if(l<=t[idx].l&&t[idx].r<=r)
	{
		add(idx,1);
		return;
	}
	pushdown(idx);
	int mid=t[idx].l+t[idx].r>>1;
	if(l<=mid)
		update(2*idx,l,r);
	if(mid+1<=r)
		update(2*idx+1,l,r);
	pushup(idx);
}
long long query(int idx,int l,int r)
{
	if(t[idx].r<l||t[idx].l>r)
		return 0;
	if(l<=t[idx].l&&t[idx].r<=r)
		return t[idx].val;
	pushdown(idx);
	int mid=t[idx].l+t[idx].r>>1;
	long long res=0;
	if(l<=mid)
		res=(res+query(2*idx,l,r))%mod;
	if(mid+1<=r)
		res=(res+query(2*idx+1,l,r))%mod;
	return res;
}
void updatepath(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])
			swap(u,v);
		update(1,dfn[top[u]],dfn[u]);
		u=fa[top[u]];
	}
	if(dep[u]>dep[v])
		swap(u,v);
	update(1,dfn[u],dfn[v]);
}
long long querypath(int u,int v)
{
	long long res=0;
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])
			swap(u,v);
		res=(res+query(1,dfn[top[u]],dfn[u]))%mod;
		u=fa[top[u]];
	}
	if(dep[u]>dep[v])
		swap(u,v);
	res=(res+query(1,dfn[u],dfn[v]))%mod;
	return res;
}
void init(int n,long long k)
{
	for(int i=1;i<=n;i++)
	{
		d[i]=ksm(i,k);
	}
	for(int i=n;i>=1;i--)
	{
		d[i]=((d[i]-d[i-1])%mod+mod)%mod;
	}
}
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>Q>>k;
	init(n,k);
	for(int i=2;i<=n;i++)
	{
		cin>>u;
		addedge(i,u);
		addedge(u,i);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	for(int i=1;i<=Q;i++)
	{
		cin>>q[i].x>>q[i].pos;
		q[i].id=i; 
	}
	sort(q+1,q+Q+1);
	cur=1;
	for(int i=1;i<=n;i++)
	{
		updatepath(1,i);
		while(cur<=Q&&q[cur].x<=i)
		{
			ans[q[cur].id]=querypath(1,q[i].pos);
			cur++;
		}
	}
	for(int i=1;i<=Q;i++)
	{
		cout<<ans[i]<<"\n";
	}
	return 0;
}
//Skadi_H