P9437 题解

xs_siqi · 2023-07-02 16:19:13 · 题解

赛时解出了。思路好想，维护细节较多的换根 dp。这道题考验了对换根 dp 模型基本掌握。

正文：本题如何运用换根 dp

换根 dp 其实是有模板的。

我总结了一下，一般情况的换根 dp 就是的过程通常是两遍 dfs，并在写题的过程中思考以下问题：

两次 dfs 前先维护两次 dfs 需要的信息
第一遍维护第二次换根过程中需要维护的信息，以及以任意一个点为根（通常为了方便取 1 号节点为根）如何得到原始 f 值（即其原始方程）
第二遍换根的转移方程
两遍 dfs 后输出的值

我们尝试使用这个模板来解决这个问题。

这题为什么是换根 dp？

此题题意可以转化为：随意确定一个点为根节点，然后计算其他节点到根节点的长度和。于是可以用换根 dp 解决。

dfs 前：两遍 dfs 前维护什么？

首先观察边权是如何得出的：两个节点点权按顺序拼起来。如何将两数拼起来？令后一个节点为 x，那么它的位数便是它对 10 取对数。所以我们得出第一个需要维护的就是一个数对 10 取对数的值（当然，你也可以不维护，直接用系统自带函数一步得出也可以）。

回到“如何拼起来”的问题，令原有数为 x，要拼的数为 y，拼起来的代价是 x\times 10^{num(y)}+y。 num 函数是该数的位数。举个例子，将 5 与 6 拼起来，6 的位数是 1，所以是 5\times 10+6=56。由此可见，我们还需维护 10 的次方倍。 由数据范围可知，我们只需要维护到 10^9 即可。

总结：维护 10 的次方倍与各个数位数。

第一遍 dfs：维护什么？原始方程是什么？

首先我们明晰这样一点：每个点到根节点的总长度，可以转化为每条边的边权乘由几个点走过这条边。即计算贡献。

这样转化有什么妙处？可以向父亲转移状态了。

我们看到我们转化后，需要记录有几个点经过一条边，显然就是这个点是多少点的祖先，也就是这个点的 size。于是我们得出第一次 dfs 需要维护每个点的 size 信息。

然后考虑原始转移方程。令 f_u 为 u 节点的所有孩子到 u 节点的总路径长度之和，那我们可以得到以下方程：

f_u=f_v\times 10^{num(u)}+p_u\times size_v

解释一下这个方程：u 是 v 的父节点，p_u 指的是 u 节点的权值，p_u\times size_v 表示有 size_v 个数经过这条边。

总结：维护 size 信息，并使用上述方程求得其他点（包括根节点，此题中点到自己本身也有距离）到根节点的距离之和。

第二次 dfs：如何运用维护的信息？方程是什么？

如何列方程？我们从最简单的情况入手。如图是 1 节点向 2 节点下移的过程。

首先考虑节点 2 的子树部分。我们发现我们需要节点 4 的 f 值作为换根后的总值。这个值在第一次 dfs 已经求过了，直接调用 f_4 即可。
然后考虑节点 2 的非其子树部分。有人可能认为可以直接调用 f_3 的值，这是不可行的。请注意，树不一定是二叉树，假如是菊花图的情况，可以把这个解法卡到 n^2。
于是很自然能想到这个思路：将根节点的 f 值减去 2 好点的 f 值。如图（图中算式有误，请手动在 10\times f_1乘号后加一个左括号，第一行最右边加上右括号），考虑最简单的情况，令 f_2 为一位数，f_1 也为一位数，那么除了 f_2 以外的 f 值显然是 f_1-10\times f_2。

两边 f 值问题已经解决。现在我们解决换根对于边的贡献问题。

首先，1 节点下所有节点及它自己少了红边。所以应为 size_2\times p_u。
其次，除了 2 节点子树以外所有节点都多了红边，所以应为 p_v\times (size_{rt}-size_v)。

那么整个方程过程就结束了。然后总结以下就是这个方程：

### 两次 dfs 后：答案是什么？ $f$ 值表示每个节点以下的点（包括自身）到其距离。那么显然就是 $f$ 数组中所有元素的和。 ### 需要注意的细节考虑到本题数据较大，所以要时时注意**取模**操作。还有例如刚刚的部分换根方程的处理： $(f_u-f_v\times 10^{num(u)}-p_u\times size_v)

若时时取模，这个地方可能会变成负数。所以我们可以直接加模数，不影响取模后结果，即变成：

(f_u+mod\times 5-f_v\times 10^{num(u)}-p_u\times size_v)

取模后结果是一致的。

附代码：

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int maxn=2e6+5;
const int mod=998244353;
int n,p[maxn],wei[maxn],ship[15],ans,f[maxn];
int fir[maxn],nxt[maxn],son[maxn],tot,q,siz[maxn];
inline void add(int x,int y){son[++tot]=y;nxt[tot]=fir[x];fir[x]=tot;}
inline void dfs1(int u,int fa){
    siz[u]=1;f[u]=p[u];//点到其本身也有距离
    for(int i=fir[u];i;i=nxt[i]){
        int v=son[i];
        if(v==fa)continue;
        dfs1(v,u);
        siz[u]+=siz[v];//维护size
        f[u]+=f[v]*ship[wei[u]]%mod+p[u]*siz[v]%mod,f[u]%=mod;}}
inline void dfs2(int u,int fa){
    for(int i=fir[u];i;i=nxt[i]){
        int v=son[i];
        if(v==fa)continue;
        f[v]=f[v]+(ship[wei[v]]%mod*((f[u]+mod*5)-f[v]*ship[wei[u]]%mod-p[u]*siz[v]%mod)%mod+(p[v]*(siz[1]-siz[v]))%mod)%mod;//只是刚刚推出来的方程多加了几个%mod
        f[v]%=mod;
        ans+=f[v],ans%=mod;
        dfs2(v,u);}}
signed main(){
    scanf("%lld",&n);
    ship[0]=1;
    for(int i=1;i<=13;i++)ship[i]=ship[i-1]*10,ship[i]%=mod;//shi p，10的几次方，不是ship小船
    for(int num,i=1;i<=n;i++){
        scanf("%lld",&p[i]);num=p[i];
        if(num==0)wei[i]=1;//wei就是位数
        else while(num)num/=10,wei[i]++;}
    for(int x,i=1;i<n;i++)scanf("%lld",&x),add(i+1,x),add(x,i+1);
    dfs1(1,0);dfs2(1,0);
    printf("%lld\n",(ans+f[1])%mod);//因为我的dfs过程只求除了f1以外的总和
    return 0;}

后文：本题对换根 dp 的启示

本题只是在边权形式上进行了创新，增加细节，换根 dp 过程本质是不变的。

所以只要熟练掌握换根dp的常见技巧过程，以及提高细节处理能力，相信换根 dp 就是常规题了。