T了,求卡常
查看原帖
T了,求卡常
1046894
hyxgg楼主2024/8/22 15:35
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
#define mod 998244353
using namespace std;
ll n,q,k;
ll fm(ll x){
	ll dc=x,re=1,mm=k;
	while(mm){
		if(mm&1) re*=dc,re%=mod;
		dc=dc*dc%mod;
		mm>>=1;
	}
	return re;
}
struct edge{
	ll q,z,xg;
}ed[500005<<1];
struct xds{
	ll l,r,z,gs,bj;
}yd[500005<<2];
struct xw{
	ll x,y,bh;
}yw[500005];
ll dd[500005],db=1,dfn[500005],ms,fa[500005],gs[500005],sd[500005],df[500005],zz[500005],cnt,qz[500005],w[500005];
void dfs1(ll root){
	ms=max(ms,sd[root]);
	gs[root]=1;
	for(ll i=dd[root];i;i=ed[i].xg){
		ll to=ed[i].z;
		if(to==fa[root])continue;
		fa[to]=root;
		sd[to]=sd[root]+1;
		dfs1(to);
		gs[root]+=gs[to];
		if(gs[to]>gs[zz[root]])zz[root]=to;
	}
}
void dfs2(ll root,ll d){
	df[root]=d;
	dfn[root]=++cnt;
	w[cnt]=root;
	if(zz[root])dfs2(zz[root],d);
	for(ll i=dd[root];i;i=ed[i].xg){
		ll to=ed[i].z;
		if(to==fa[root]||to==zz[root])continue;
		dfs2(to,to);
	}
}
void js(ll b,ll l,ll r){
	yd[b].l=l,yd[b].r=r;
	if(l==r){
		return;
	}
	ll mid=(l+r)>>1;
	js(b<<1,l,mid);
	js(b<<1|1,mid+1,r);
	return ;
}
bool cmp(xw a,xw b){
	return a.x<b.x;
}
void down(ll b){
	yd[b<<1].bj+=yd[b].bj;
	yd[b<<1].bj%=mod;
	yd[b<<1|1].bj+=yd[b].bj;
	yd[b<<1].bj%=mod;
	yd[b<<1].z+=yd[b].bj*(qz[yd[b<<1].r]-qz[yd[b<<1].l-1])%mod;
	yd[b<<1].z%=mod;
	yd[b<<1|1].z+=yd[b].bj*(qz[yd[b<<1|1].r]-qz[yd[b<<1|1].l-1])%mod;
	yd[b<<1|1].z%=mod;
	yd[b].bj=0;
}
void gd(ll b,ll x,ll y){
	if(yd[b].l>=x&&yd[b].r<=y){
		yd[b].bj++;
		yd[b].z+=qz[yd[b].r]-qz[yd[b].l-1];
		yd[b].z%=mod;
		return ;
	}
	if(yd[b].bj)down(b);
	if(yd[b<<1].r>=x)gd(b<<1,x,y);
	if(yd[b<<1|1].l<=y)gd(b<<1|1,x,y);
	yd[b].z=(yd[b<<1].z+yd[b<<1|1].z)%mod;
}
ll cx(ll b,ll x,ll y){
	if(yd[b].l>=x&&yd[b].r<=y){
		return yd[b].z;
	}
	if(yd[b].bj)down(b);
	ll s=0;
	if(yd[b<<1].r>=x)s+=cx(b<<1,x,y);
	s%=mod;
	if(yd[b<<1|1].l<=y)s+=cx(b<<1|1,x,y);
	s%=mod;
	return s;
}
void fjq(ll q,ll z){
	ed[db].q=q,ed[db].z=z,ed[db].xg=dd[q],dd[q]=db++;
}
ll read(){
	char c=getchar();
	ll s=0;
	while(c<'0'||c>'9')c=getchar();
	while(c<='9'&&c>='0'){
		s=s*10+c-'0';
		c=getchar();
	}
	return s;
}
ll ans[500005],mm[500005];
int main(){
	n=read(),q=read(),k=read();
	ll aa,bb;
	for(ll i=2;i<=n;i++){
		aa=read();
		fjq(i,aa),fjq(aa,i);
	}
	sd[1]=qz[1]=1;
	dfs1(1);
	dfs2(1,1);
	for(ll i=1;i<=ms;i++){
		mm[i]=fm(i);
	}
	for(ll i=2;i<=n;i++){
		qz[i]=qz[i-1]+(mm[sd[w[i]]]-mm[sd[w[i]]-1])%mod;
		qz[i]%=mod;
	}
	js(1,1,n);
	for(ll i=1;i<=q;i++){
		yw[i].x=read(),yw[i].y=read();
		yw[i].bh=i;
	}
	sort(yw+1,yw+1+n,cmp);
	for(ll i=1,j=1;i<=q;i++){
		ll ti=i;
		while(df[ti]!=1){
			gd(1,dfn[df[ti]],dfn[ti]);
			ti=fa[df[ti]];
		}
		gd(1,1,dfn[ti]);
		while(j<=n&&yw[j].x==i){
			ll da=0;
			ti=yw[j].y;
			while(df[ti]!=1){
				da+=cx(1,dfn[df[ti]],dfn[ti]);
				da%=mod;
				ti=fa[df[ti]];
			}
			da+=cx(1,1,dfn[ti]);
			da%=mod;
			da+=mod;
			da%=mod;
			ans[yw[j].bh]=da;
			j++;
		}
	}
	for(ll i=1;i<=q;i++){
		printf("%lld\n",ans[i]);
	}
	return 0;
}
2024/8/22 15:35
加载中...