自动搬运

查看原文

来自洛谷，原作者为

	x义x “我们要走多远？”“一百万年。”

搬运于2025-08-24 22:09:19，当前版本为作者最后更新于2019-09-11 20:29:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$$\color{green}\Large\texttt{『菜鸡的blog』}$$

如果$k=1$，那么就是一道原题：P4211 [LNOI2014]LCA，顺便挂一下我此题的题解：click here。下面的讲解以这题为基础。

在上面那道题中，我们提到，要对$u$到根的路径上所有点+1，$v$到根的路径的权值就是$u,v$的LCA的深度（的1次方）。修改和查询使用树剖再加线段树维护。

思考$k\neq1$的情况。原来$k=1$的+1是从哪里来的？深度从$d$变成$d+1$，对答案的贡献就会增长$(d+1)^1-d^1=1$，所以我们+1。

如果把1改成$k$呢？$(d+1)^k-d^k=\dots$算了我们也不是很关心柿子，反正每个点的深度只有一个，直接算出来就好了。

现在的问题是，我们需要用线段树维护一个序列，使得我们可以：

• 对$[l,r]$的每一个数加$A[i]=dep[i]^k-(dep[i]-1)^k$

• 求$[l,r]$的区间和

这非常sb，处理出每个区间$[l,r]$的$\sum _{i=l}^rA[i]$就可以轻松维护了。

代码如下。

#include<bits/stdc++.h>
using namespace std;

const int tt=998244353;

int N,M,K;
int lnk[50005];
int pre[50005],tgt[50005],cnt;
void add_E(int u,int v){
	pre[++cnt]=lnk[u],tgt[cnt]=v,lnk[u]=cnt;
}

int fa[50005],son[50005],s[50005],dep[50005];
int top[50005],seg[50005],rev[50005],idx;
void dfs1(int x){
	s[x]=1;dep[x]=dep[fa[x]]+1;
	for(int e=lnk[x];e;e=pre[e]){
		dfs1(tgt[e]),s[x]+=s[tgt[e]];
		if(s[tgt[e]]>s[son[x]]) son[x]=tgt[e];
	}
}
void dfs2(int x){
	seg[x]=++idx;rev[idx]=x;
	if(son[x]) top[son[x]]=top[x],dfs2(son[x]);
	for(int e=lnk[x];e;e=pre[e])if(tgt[e]!=son[x])
		top[tgt[e]]=tgt[e],dfs2(tgt[e]);
}

int A[50005];

int ANS[50005];
struct Qs{
	int u,v,pos;
	bool operator <(const Qs b)const{return u<b.u;}
}Q[50005];

int Key[200005],Sum[200005],Lzy[200005];
void push_up(int x){Sum[x]=(Sum[x<<1]+Sum[x<<1|1])%tt;}
void push_down(int x,int l,int r){
	int mid=(l+r)>>1;
	Sum[x<<1]=(Sum[x<<1]+1LL*Key[x<<1]*Lzy[x]%tt)%tt;
	Lzy[x<<1]=(Lzy[x<<1]+Lzy[x])%tt;
	Sum[x<<1|1]=(Sum[x<<1|1]+1LL*Key[x<<1|1]*Lzy[x]%tt)%tt;
	Lzy[x<<1|1]=(Lzy[x<<1|1]+Lzy[x])%tt;
	Lzy[x]=0;
}
void Build(int x,int l,int r){
	if(l==r){Key[x]=A[rev[l]];return;}
	int mid=(l+r)>>1;
	Build(x<<1,l,mid);Build(x<<1|1,mid+1,r);
	Key[x]=(Key[x<<1]+Key[x<<1|1])%tt;
}
void Update(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R){Sum[x]=(Sum[x]+Key[x]%tt)%tt;Lzy[x]=(Lzy[x]+1)%tt;return;}
	push_down(x,l,r);
	int mid=(l+r)>>1;
	if(L<=mid) Update(x<<1,l,mid,L,R);
	if(R>mid) Update(x<<1|1,mid+1,r,L,R);
	push_up(x);
}
int Query(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R) return Sum[x];
	push_down(x,l,r);
	int mid=(l+r)>>1,ans=0;
	if(L<=mid) ans=(ans+Query(x<<1,l,mid,L,R))%tt;
	if(R>mid) ans=(ans+Query(x<<1|1,mid+1,r,L,R))%tt;
	push_up(x);
	return ans;
}

void Chain_Update(int x){
	while(x){
		Update(1,1,N,seg[top[x]],seg[x]);
		x=fa[top[x]];
	}
}
int Chain_Query(int x){
	int ans=0;
	while(x){
		ans=(ans+Query(1,1,N,seg[top[x]],seg[x]))%tt;
		x=fa[top[x]];
	}
	return ans;
}

int now_id=1;
int qpow(int a,int k){
	int ans=1;
	while(k){
		if(k&1) ans=1LL*ans*a%tt;
		a=1LL*a*a%tt;
		k>>=1;
	}
	return ans;
}

int main(){
	scanf("%d%d%d",&N,&M,&K);
	fa[1]=0;
	for(int i=2;i<=N;i++) scanf("%d",&fa[i]),add_E(fa[i],i);
	dfs1(1);top[1]=1;dfs2(1);
	for(int i=1;i<=N;i++) A[i]=(qpow(dep[i],K)-qpow(dep[i]-1,K)+tt)%tt;
	Build(1,1,N);
	for(int i=1;i<=M;i++){
		int r,z;scanf("%d%d",&r,&z);
		Q[i].u=r,Q[i].v=z,Q[i].pos=i;
	}
	sort(Q+1,Q+M+1);
	for(int i=1;i<=N;i++){
		Chain_Update(i);
		while(Q[now_id].u==i&&now_id<=M){
			ANS[Q[now_id].pos]=Chain_Query(Q[now_id].v);
			now_id++;
		}
	}
	for(int i=1;i<=M;i++) printf("%d\n",ANS[i]);
	
	return 0;
}