题解 P5439 【【XR-2】永恒】

· · 题解

如果没有 subtask 时间取 min 的机制，这份代码将跑得比所有代码都快得多。。。

首先看到这题一眼边分治 + 虚树上 dp，后来看到没有保证 d_i 互不相等就不会搞了。。。

算了，老老实实算贡献吧。

我们对于每个点对 (x,y) 算它的贡献。

x,y\not =LCA(x,y)$，贡献是 $siz_x\times siz_y\times dep_{LCA(x,y)}

不妨令 x=LCA(x,y)，那么若 z 是 x\rightarrow y 路径的第二个点，贡献是 (n-siz_z)\times siz_y\times dep_{LCA(x,y)}

因为三个东西乘起来不好处理，我们把 dep 这个限制差分一下，把 y\rightarrow rt 加 siz_y，然后枚举 x，求 x\rightarrow rt 的和，乘上 siz_x。

第一个部分的贡献是可以离线处理的，时间复杂度 O(n)/O(n\log n)，你可以像我一样求和那部分直接预处理 dfs 序前缀和后暴力向上跳。

当然，第一个部分的贡献我们多算了，我们要在第二部分减掉。

第二个部分的贡献就暴力多了，假设 dfs 的时候遍历的是 x\rightarrow y 这条边，我们把 d_x\rightarrow rt 加 n-siz_y-siz_x，遍历完 y 的子树后减去这个值，然后遍历到一个点暴力向上跳就行了。

时间复杂度 O(n\log^2 m)，而且这一个是树剖的 \log 一个是线段树/树状数组的 \log，常数极小就对了。

Code\ Below: 
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int maxn=300000+10;
const int mod=998244353;
int n,m,rt,a[maxn],fa[maxn],siz[maxn],ans,head[maxn],to[maxn<<1],nxt[maxn<<1],tot;

namespace Tree
{
int c[2][maxn],w[maxn],val[maxn],head[maxn],to[maxn],nxt[maxn],tot;
int top[maxn],dep[maxn],siz[maxn],son[maxn],fa[maxn],id[maxn],mp[maxn],tim;
#define lowbit(x) ((x)&(-(x)))
inline void add(int *c,int x,int y)
{
    for(;x<=m;x+=lowbit(x)) c[x]=(c[x]+y)%mod;
}
inline int Ask(int *c,int x)
{
    int ans=0;
    for(;x;x-=lowbit(x)) ans=(ans+c[x])%mod;
    return ans;
}
inline void Update(int x,int v) {add(c[0],x,v);add(c[1],x,1ll*(x-1)*v%mod);}
inline void update(int l,int r,int v) {Update(l,v);Update(r+1,mod-v);}
inline int Query(int x) {return (1ll*x*Ask(c[0],x)%mod-Ask(c[1],x)+mod)%mod;}
inline int query(int l,int r) {return (Query(r)-Query(l-1)+mod)%mod;}
inline void modify(int x,int y)
{
    for(;x;x=fa[top[x]]) update(id[top[x]],id[x],y);
}
inline int ask(int x)
{
    int ans=0;
    for(;x;x=fa[top[x]]) ans=(ans+query(id[top[x]],id[x]))%mod;
    return ans;
}
inline int ask_pre(int x)
{
    int ans=0;
    for(;x;x=fa[top[x]]) ans=(ans+(val[id[x]]-val[id[top[x]]-1]+mod)%mod)%mod;
    return ans;
}
inline void addedge(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
void dfs1(int x,int f)
{
    siz[x]=1;fa[x]=f;dep[x]=dep[f]+1;
    int maxson=-1;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];
        dfs1(y,x);siz[x]+=siz[y];w[x]=(w[x]+w[y])%mod;
        if(siz[y]>maxson) maxson=siz[y],son[x]=y;
    }
}
void dfs2(int x,int topf)
{
    id[x]=++tim;mp[tim]=x;top[x]=topf;
    if(son[x]) dfs2(son[x],topf);
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];
        if(y==son[x]) continue;
        dfs2(y,y);
    }
}
inline void init()
{
    scanf("%d",&fa[1]);
    for(int i=2;i<=m;i++) scanf("%d",&fa[i]),addedge(fa[i],i);
    scanf("%*s");
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) w[a[i]]=(w[a[i]]+::siz[i])%mod;
    for(int i=head[1];i;i=nxt[i]) dfs1(to[i],0),dfs2(to[i],to[i]);
    for(int i=1;i<=m;i++) val[i]=w[mp[i]];
    for(int i=1;i<=m;i++) val[i]=(val[i]+val[i-1])%mod;
}
}

inline void addedge(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
void dfs(int x)
{
    siz[x]=1;
    for(int i=head[x];i;i=nxt[i]) dfs(to[i]),siz[x]+=siz[to[i]];
}
void dfs1(int x)
{
    ans=(ans+1ll*Tree::ask(a[x])*siz[x]%mod)%mod;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];
        Tree::modify(a[x],(n-siz[y]-siz[x]+mod)%mod);
        dfs1(y);
        Tree::modify(a[x],(siz[y]+siz[x]-n+mod)%mod);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&fa[i]);
        if(!fa[i]) rt=i;
        else addedge(fa[i],i);
    }
    dfs(rt);Tree::init();
    for(int i=1;i<=n;i++)
    {
        ans=(ans+1ll*Tree::ask_pre(a[i])*siz[i]%mod)%mod;
        ans=(ans+1ll*siz[i]*siz[i]%mod*(mod-Tree::dep[a[i]])%mod)%mod;
    }
    ans=1ll*ans*((mod+1)>>1)%mod;dfs1(rt);
    printf("%d\n",ans);
    return 0;
}