[洛谷 5305][GXOI/GZOI2019]旧词

题目链接

https://www.luogu.com.cn/problem/P5305

题解

本题显然是 [LNOI2014]LCA 的推广。

我们还是采用和那道题一样的方法来维护 LCA 深度和。唯一的区别就在于对 $k$ 次方这个操作的处理上。

先思考一下 $k=1$ 的情况，我们将路径上所有节点的值加一，究竟是为什么呢？

其实这个操作可以视为一个树上差分的操作。我们执行的修改操作，其实是给点权加上相邻两点深度的差值（$k=1$ 时显然就是 $1$），而把差分数组累加起来，则就是要求的和。

理解了这一点，我们也不难把这个操作推广到 $k \neq 1$ 的情况了。根据上文所述，对于一个深度为 $dep_i$ 的点，我们执行一次修改操作给它的点权加上的值为 $dep_i^k-(dep_i-1)^k$。

这样我们就完美地解决了本题。

#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 998244353
using namespace std;
struct query
{
 int r,z,id;
 bool operator<(const query&a)const
 {
  return r<a.r;
 }
};
struct seg
{
 long long sum,tag,ds;
}s[200005];
struct edge
{
 int v,next;
}e[50005];
vector<query> q;
int n,Q,k;
int head[50005],ans[50005];
int siz[50005],dep[50005],son[50005],fa[50005],num[50005];
int id[50005],top[50005],cnt;
int dk[50005];
long long fpow(long long x,long long y)
{
 long long ans=1;
 while(y)
 {
  if(y&1)ans=ans*x%MOD;
  x=x*x%MOD;
  y>>=1;
 }
 return ans;
}
void addedge(int u,int v)
{
 e[++cnt].v=v;
 e[cnt].next=head[u];
 head[u]=cnt;
}
void dfs1(int u,int f)
{
 siz[u]=1;
 dep[u]=dep[f]+1;
 for(int i=head[u];i;i=e[i].next)
 {
  int v=e[i].v;
  dfs1(v,u);
  siz[u]+=siz[v];
  if(siz[v]>siz[son[u]])son[u]=v;
 }
}
void dfs2(int u,int t)
{
 id[u]=++cnt;
 num[cnt]=u;
 top[u]=t;
 if(!son[u])return;
 dfs2(son[u],t);
 for(int i=head[u];i;i=e[i].next)
  if(e[i].v!=son[u])dfs2(e[i].v,e[i].v);
}
void pushup(int root)
{
 s[root].sum=(s[root<<1].sum+s[root<<1|1].sum)%MOD;
 s[root].ds=(s[root<<1].ds+s[root<<1|1].ds)%MOD;
}
void build(int root,int l,int r)
{
 if(l==r)
 {
  s[root].ds=dk[num[l]];
  return;
 }
 int mid=(l+r)>>1;
 build(root<<1,l,mid);
 build(root<<1|1,mid+1,r);
 pushup(root);
}
void pushdown(int root)
{
 s[root<<1].tag+=s[root].tag;s[root<<1].tag%=MOD;
 s[root<<1|1].tag+=s[root].tag;s[root<<1|1].tag%=MOD;
 s[root<<1].sum+=s[root].tag*s[root<<1].ds%MOD;s[root<<1].sum%=MOD;
 s[root<<1|1].sum+=s[root].tag*s[root<<1|1].ds%MOD;s[root<<1|1].sum%=MOD;
 s[root].tag=0;
}
void update(int root,int cl,int cr,int l,int r)
{
 if(r<cl||cr<l)return;
 if(l<=cl&&cr<=r)
 {
  s[root].tag++;
  s[root].sum=(s[root].sum+s[root].ds)%MOD;
  return;
 }
 pushdown(root);
 int mid=(cl+cr)>>1;
 update(root<<1,cl,mid,l,r);
 update(root<<1|1,mid+1,cr,l,r);
 pushup(root);
}
int query(int root,int cl,int cr,int l,int r)
{
 if(r<cl||cr<l)return 0;
 if(l<=cl&&cr<=r)return s[root].sum;
 pushdown(root);
 int mid=(cl+cr)>>1;
 return (query(root<<1,cl,mid,l,r)+query(root<<1|1,mid+1,cr,l,r))%MOD;
}
void update_chain(int x,int y)
{
 while(top[x]!=top[y])
 {
  if(dep[top[x]]<dep[top[y]])swap(x,y);
  update(1,1,n,id[top[x]],id[x]);
  x=fa[top[x]];
 }
 if(dep[x]>dep[y])swap(x,y);
 update(1,1,n,id[x],id[y]);
}
int query_chain(int x,int y)
{
 int ans=0;
 while(top[x]!=top[y])
 {
  if(dep[top[x]]<dep[top[y]])swap(x,y);
  ans=(ans+query(1,1,n,id[top[x]],id[x]))%MOD;
  x=fa[top[x]];
 }
 if(dep[x]>dep[y])swap(x,y);
 ans=(ans+query(1,1,n,id[x],id[y]))%MOD;
 return ans;
}
int main()
{
 ios::sync_with_stdio(false);
 cin>>n>>Q>>k;
 for(int i=2;i<=n;i++)
 {
  cin>>fa[i];
  addedge(fa[i],i);
 }
 cnt=0;
 dfs1(1,1);
 dfs2(1,1);
 for(int i=1;i<=n;i++)
  dk[i]=(fpow(dep[i],k)-fpow(dep[i]-1,k)+MOD)%MOD;
 build(1,1,n);
 for(int i=1;i<=Q;i++)
 {
  int r,z;
  cin>>r>>z;
  q.push_back({r,z,i});
 }
 sort(q.begin(),q.end());
 int u=1;
 for(auto i:q)
 {
  while(u<=i.r)
  {
   update_chain(1,u);
   u++;
  }
  ans[i.id]=query_chain(1,i.z);
 }
 for(int i=1;i<=Q;i++)
  cout<<(ans[i]+MOD)%MOD<<endl;
 return 0;
}