洛谷5305 [GXOI/GZOI2019]旧词

题意

给出一棵树，定义 $\mathrm{dep}[i]$ 为 $i$ 的深度，$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。

有形如 $\text{(x y)}$ 的询问，求 $\sum\limits_{i \le x} \text{dep}(\text{LCA}(i,y))^k$ 。

其中点数 $N\le 50000$ ，询问数 $M\le 50000$ 。

题解

跟 洛谷4211 [LNOI2014]LCA 差不多（省选原题海星）

区别只有最后统计答案不需要差分，但变成了 $k$ 次方。

$k=1$

直接将那道题把差分删掉即可。

$k > 1$

原题中对路径 $+1$ 的本质时树上差分，即 $\text{dep} [x]^{1}-(\text{dep} [x]-1)^{1}$ 。

那么这里需要改成 $\text{dep} [x]^{k}-(\text{dep} [x]-1)^{k}$ 。

考虑线段树中多加一个变量 $pre$ ，值为 $\text{dep} [x]^{k}-(\text{dep} [x]-1)^{k}$ ， $\text{pushup()}$ 时向上累加， 修改时直接加上即可。

因为 $k\le 10^{9}$ ，所以需要快速幂。而且模数相乘肯定会爆 $\text{int}$ ，所以为了省事我全部开的 $\text{long long}$ 。

#include<bits/stdc++.h>
#define ll long long
#define ha 998244353

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    ll next,to;
} edge[50005];
struct Tree {
    ll left,right,sum,delta,pre;
} tree[200005];
struct Q {
    ll i,pos,z;
} q[50005];
ll cnt,head[50005],n,m,k,a,ans[50005],ord[50005];
ll dfsord,siz[50005],fa[50005],son[50005],deep[50005],top[50005],id[50005];

inline void add(ll u,ll v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline ll POW(ll x,ll y)
{
    ll ans=1;
    while (y)
    {
        if (y&1) ans=ans*x%ha;
        y>>=1;
        x=x*x%ha;
    }
    return ans%ha;
}

inline void pushup(ll x)
{
    tree[x].sum=(tree[x*2].sum+tree[x*2+1].sum)%ha;
    tree[x].pre=(tree[x*2].pre+tree[x*2+1].pre)%ha;
}

inline void pushdown(ll x)
{
    tree[x*2].sum=(tree[x*2].sum+tree[x*2].pre*tree[x].delta)%ha;
    tree[x*2+1].sum=(tree[x*2+1].sum+tree[x*2+1].pre*tree[x].delta)%ha;
    tree[x*2].delta=(tree[x*2].delta+tree[x].delta)%ha;
    tree[x*2+1].delta=(tree[x*2+1].delta+tree[x].delta)%ha;
    tree[x].delta=0;
}

void build(ll x,ll l,ll r)
{
    tree[x].left=l;
    tree[x].right=r;
    if (r-l==1) tree[x].pre=(POW(deep[ord[l]],k)-POW(deep[ord[l]]-1,k)+ha)%ha;
    else
    {
        ll mid=(l+r)>>1;
        build(x*2,l,mid);
        build(x*2+1,mid,r);
        pushup(x);
    }
}

void update(ll x,ll l,ll r)
{
    if (l<=tree[x].left && r>=tree[x].right)
    {
        tree[x].sum=(tree[x].sum+tree[x].pre)%ha;
        tree[x].delta++;
    }
    else
    {
        if (tree[x].delta) pushdown(x);
        ll mid=(tree[x].left+tree[x].right)>>1;
        if (l<mid) update(x*2,l,r);
        if (r>mid) update(x*2+1,l,r);
        pushup(x);
    }
}

ll query(ll x,ll l,ll r)
{
    if (l<=tree[x].left && r>=tree[x].right) return tree[x].sum;
    else
    {
        if (tree[x].delta) pushdown(x);
        ll mid=(tree[x].left+tree[x].right)>>1,ans=0;
        if (l<mid) ans=(ans+query(x*2,l,r))%ha;
        if (r>mid) ans=(ans+query(x*2+1,l,r))%ha;
        return ans;
    }
}

void dfs1(ll x,ll f,ll dep)
{
    fa[x]=f;
    deep[x]=dep;
    siz[x]=1;
    ll mx=0;
    for (ll i=head[x];i;i=edge[i].next)
    {
        ll y=edge[i].to;
        if (y==f) continue;
        dfs1(y,x,dep+1);
        siz[x]+=siz[y];
        if (siz[x]>mx)
        {
            mx=siz[x];
            son[x]=y;
        }
    }
}

void dfs2(ll x,ll topf)
{
    top[x]=topf;
    id[x]=++dfsord;
    ord[dfsord]=x;
    if (!son[x]) return;
    dfs2(son[x],topf);
    for (ll i=head[x];i;i=edge[i].next)
    {
        ll y=edge[i].to;
        if (y==fa[x] || y==son[x]) continue;
        dfs2(y,y);
    }
}

inline void upRange(ll u,ll v)
{
    while (top[u]!=top[v])
    {
        if (deep[top[u]]<deep[top[v]]) swap(u,v);
        update(1,id[top[u]],id[u]+1);
        u=fa[top[u]];
    }
    if (deep[u]>deep[v]) swap(u,v);
    update(1,id[u],id[v]+1);
}

inline ll qRange(ll u,ll v)
{
    ll ans=0;
    while (top[u]!=top[v])
    {
        if (deep[top[u]]<deep[top[v]]) swap(u,v);
        ans=(ans+query(1,id[top[u]],id[u]+1))%ha;
        u=fa[top[u]];
    }
    if (deep[u]>deep[v]) swap(u,v);
    ans=(ans+query(1,id[u],id[v]+1))%ha;
    return ans;
}

inline bool cmp(Q x,Q y) { return x.pos<y.pos; }

int main()
{
    n=read(); m=read(); k=read();
    for (ll i=2;i<=n;i++)
    {
        a=read();
        add(a,i);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,n+1);
    for (ll i=1;i<=m;i++) q[i].i=i,q[i].pos=read(),q[i].z=read();
    sort(q+1,q+m+1,cmp);
    ll j=0;
    for (ll i=1;i<=m;i++)
    {
        while (j<q[i].pos) upRange(1,++j);
        ans[q[i].i]=qRange(1,q[i].z);
    }
    for (ll i=1;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}