题目描述
acwing3035的加强版,考虑每个点对父节点的贡献,在原题中只用考虑k=1的情况,用差分的思想将每个点的深度分散到该点到根节点的路径上,那就是路径上每个点权值都增加一,查询时把询问的点的所有父节点的路径累加起来即可,这题需要稍作变化。
可以用主席树在线处理询问,由于acwing上这题给的内存比较少,就离线下来排序完求就行(这里用标记永久化的线段树来维护)。
时间复杂度
O(nlog^2(n))
C++ 代码
#pragma GCC optimize(1,2,3,"Ofast","inline")
#include<iostream>
#include<cmath>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<set>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<string>
using namespace std;
#define ls(u) tr[u].son[0]
#define rs(u) tr[u].son[1]
const int N=1e5+505,M=1e7+10,L=350,INF=0x3f3f3f3f,mod=998244353;
const double alpha=0.725,eps=1e-8;
typedef long long LL;
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline int read(){
int x=0,f=1;char ch=nc();
while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}
if(ch=='-')f=-1;
while(ch>=48&&ch<=57)x=(x<<1)+(x<<3)+(ch^48),ch=nc();
return f*x;
}
inline void write(int x){
if(x<10)putchar(x^48);
else write(x/10),write(x%10);
}
int pt;
inline void read(char* opt){
char ch=nc();
while(ch<65||ch>132||ch>90&&ch<97)ch=nc();
while(ch>=65&&ch<=90||ch>=97&&ch<=132||ch=='-')opt[pt++]=ch,ch=nc();
opt[pt]=0,pt=0;
}
int n,m,k;
int h[N],e[2*N],ne[2*N],idx;
inline int qmi(int a){
int res=1,b=k;
while(b){
if(b&1)res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
inline void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int sz[N],dep[N],son[N],fa[N];
inline void dfs1(int u,int p){
sz[u]=1,dep[u]=dep[p]+1,fa[u]=p;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==p)continue;
dfs1(j,u);
sz[u]+=sz[j];
if(sz[j]>sz[son[u]])son[u]=j;
}
}
int q[N],id[N],top[N],cnt;
inline void dfs2(int u,int p,int t){
q[++cnt]=u,id[u]=cnt,top[u]=t;
if(son[u])dfs2(son[u],u,t);
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==p||j==son[u])continue;
dfs2(j,u,j);
}
}
struct Query{
int x,y,id;
inline bool operator<(const Query& t)const {
return x<t.x;
}
}a[N];
struct Node{
int l,r,v;
int sum,add;
}tr[4*N];
int pre[N];
inline void build(int u,int l,int r){
tr[u].l=l,tr[u].r=r;
if(l==r){
tr[u].v=(qmi(dep[q[l]])-qmi(dep[q[l]]-1))%mod;
return ;
}
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
tr[u].v=(tr[u<<1].v+tr[u<<1|1].v)%mod;
}
inline void update(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r){
tr[u].add++,tr[u].sum=(tr[u].sum+tr[u].v)%mod;
return ;
}
int mid=tr[u].l+tr[u].r>>1;
tr[u].sum=(tr[u].sum+(pre[min(r,tr[u].r)]-pre[max(l,tr[u].l)-1])%mod)%mod;
if(l<=mid)update(u<<1,l,r);
if(r>mid)update(u<<1|1,l,r);
}
inline int query(int u,int l,int r,int add){
if(tr[u].l>=l&&tr[u].r<=r)return (tr[u].sum+1ll*add*tr[u].v)%mod;
int mid=tr[u].l+tr[u].r>>1,res=0;
if(l<=mid)res+=query(u<<1,l,r,add+tr[u].add);
if(r>mid)res+=query(u<<1|1,l,r,add+tr[u].add);
return res%mod;
}
inline void update(int x){
while(x){
update(1,id[top[x]],id[x]);
x=fa[top[x]];
}
}
inline int query(int x){
int res=0;
while(x){
res=(res+query(1,id[top[x]],id[x],0))%mod;
x=fa[top[x]];
}
return res;
}
int ans[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
memset(h,-1,sizeof h);
n=read(),m=read(),k=read();
for(int i=2;i<=n;i++){
int p=read();
add(i,p),add(p,i);
}
dfs1(1,0),dfs2(1,0,1);
build(1,1,n);
for(int i=1;i<=n;i++)pre[i]=(pre[i-1]+(qmi(dep[q[i]])-qmi(dep[q[i]]-1))%mod)%mod;
for(int i=1;i<=m;i++){
int x=read(),y=read();
a[i]={x,y,i};
}
sort(a+1,a+m+1);
for(int i=1,j=1;i<=m;i++){
while(j<=n&&j<=a[i].x)update(j++);
ans[a[i].id]=query(a[i].y);
}
for(int i=1;i<=m;i++)write((ans[i]%mod+mod)%mod),putchar('\n');
}