题解 P5305 【[GXOI/GZOI2019]旧词】

· · 题解

\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算了我们也不是很关心柿子，反正每个点的深度只有一个，直接算出来就好了。

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

这非常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;
}