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

· · 题解

不同于其他题解的树链剖分+树状数组做法。

第一步还是离线，然后按照x从小到大插入。

我们考虑询问y时，y到根路径上的每个节点的贡献。

令sz_i表示当前以节点i为根的子树中，已经被插入的数的个数。

则y的贡献为dep(y)^k\times sz_y，而y的祖先z的贡献为dep(y)^k\times (sz_z-sz_p)，其中p为y到根的路径中，最浅的比z深的节点。

如果y到根是一条重链，那么我们只需要对每个点维护轻儿子的子树贡献和S_x（包括自己本身），然后用数据结构维护就好了。

所以我们对原树进行树链剖分，每次询问都是若干段重链和若干条轻边。重链上的我们直接在数据结构上查，轻边上的特殊处理一下就好了。

我们具体来看一下如何维护：

考虑新插入一个节点x，则其到根路径上的每个点的子树节点个数都要加1。而S中需要变化的节点只有节点x本身和每条轻边的顶。

考虑查询一个节点，对于每条轻边顶的点，我们已经维护了每个点的子树大小，所以可以直接计算出其真实有贡献的节点个数，然后统计进答案。其他的点的贡献在S中已经维护，直接查询即可。

所以我们需要一个资瓷区间修改，单点查询的数据结构和一个资瓷单点修改，区间查询的数据结构。

两者都可以用树状数组。

时间复杂度O(n\log^2 n)。

在2019年4月23日拿到当时洛谷和LOJ的双最优解。

加那个读入优化纯属是因为强迫症，不加也是当时最优解

Code：

#include<cstdio>
#include<cctype>
#include<algorithm>
typedef long long LL;
const int md=998244353,N=50005;
char buf[(int)5e6],*ss=buf;
inline void init(){buf[fread(buf,1,(int)5e6-1,stdin)]='\n';fclose(stdin);}
inline int readint(){
    int d=0;
    while(!isdigit(*ss))++ss;
    while(isdigit(*ss))d=d*10+(*ss++&15);
    return d;
}
int n,Q,k,fa[N],head[N],cnt,ans[N],dep[N],sz[N],top[N],son[N],dfn[N],idx,dp[N];
int b1[N],b2[N],c[N];
inline void upd(int&a){a+=a>>31&md;}
inline void add1(int i,int x){for(;i<=n;i+=i&-i)b1[i]+=x;}
inline int ask1(int i){int x=0;for(;i;i^=i&-i)x+=b1[i];return x;}
inline void add2(int i,int x){for(x>0?x-=md:0;i<=n;i+=i&-i)upd(b2[i]+=x);}
inline int ask2(int i){int x=0;for(;i;i^=i&-i)upd(x+=b2[i]-md);return x;}
struct edge{
    int to,nxt;
}e[N];
inline int pow(int a){
    int ret=1,b=k;
    for(;b;b>>=1,a=(LL)a*a%md)if(b&1)ret=(LL)ret*a%md;
    return ret;
}
struct que{
    int x,y,id;
    inline bool operator<(const que&rhs)const{return x<rhs.x;}
}q[N];
void dfs(int now){
    sz[now]=1,son[now]=0;
    for(int i=head[now];i;i=e[i].nxt){
        dep[e[i].to]=dep[now]+1,dfs(e[i].to),sz[now]+=sz[e[i].to];
        if(!son[now]||sz[son[now]]<sz[e[i].to])son[now]=e[i].to;
    }
}
void dfs2(int now){
    dfn[now]=++idx;
    if(son[now])top[son[now]]=top[now],dfs2(son[now]);
    for(int i=head[now];i;i=e[i].nxt)
    if(e[i].to!=son[now])dfs2(top[e[i].to]=e[i].to);
}
void add(int x){
    for(;x;x=fa[top[x]])
    add1(dfn[top[x]],1),add1(dfn[x]+1,-1),
    add2(dfn[x],-c[x]),add2(dfn[x],c[x]=(LL)dp[x]*(ask1(dfn[x])-ask1(dfn[son[x]]))%md);
}
int query(int x){
    int ret=0,pre=0;
    for(;x;x=fa[top[x]]){
        ret=(ret+(LL)dp[x]*(ask1(dfn[x])-ask1(dfn[pre])))%md;
        if(x!=top[x])x=fa[x],upd(ret+=ask2(dfn[x])-md),upd(ret-=ask2(dfn[top[x]]-1));
        pre=top[x];
    }
    return ret;
}
int main(){
    init();
    n=readint(),Q=readint(),k=readint();
    for(int i=2;i<=n;++i)
    e[++cnt]=(edge){i,head[fa[i]=readint()]},head[fa[i]]=cnt;
    dfs(dep[1]=1),dfs2(top[1]=1);
    for(int i=1;i<=n;++i)dp[i]=pow(dep[i]);
    for(int i=1;i<=Q;++i)q[i].x=readint(),q[q[i].id=i].y=readint();
    std::sort(q+1,q+Q+1);
    for(int i=1,x=0;i<=Q;++i){
        while(x<q[i].x)
        add(++x);
        ans[q[i].id]=query(q[i].y);
    }
    for(int i=1;i<=Q;++i)
    printf("%d\n",ans[i]);
    return 0;
}