题解：P11492 [BalticOI 2023] Minequake
fish_ysj
·
·
题解
P11492 [BalticOI 2023] Minequake题解
本题解公式较多，建议前往洛谷传送门观看。
本题解最终状态转移相较其他题解更加简单。
题目大意
题目描述的十分简洁易懂了，自己看题。本题解注重思路梳理和状态转移方程的推导。P11492 [BalticOI 2023] Minequake
思路
初步思路
看到这种树上求最小值的题目首先考虑树形 DP。又由于我比较菜，所以我们不妨先考虑已知起点的情况：
先假设以 1 号节点为根节点和起点，显然我们要思考以何种顺序遍历子树。我们当然可以先假设优先遍历子节点较少的子树是更优（其实稍加思考过后发现无论如何遍历子树对最终答案都没有影响，这一点在后文也会证明）。此时，我们就可以想到用一个数组 siz[x] 表示 x 子树的大小（包括 x 本身）
接下来，既然是 DP，那就让我们来定义一个状态。
DP 状态定义
定义：dp[x] 表示 x 子树中所有子节点（包括 x 号节点）第一次被访问到的时间和。
这时候问题来了：时间和是由起始节点的位置决定的，在目前的思路中是由 1 号节点的位置决定，那么就无法完成子树内部独立的状态转移，违背了 DP 的初衷。那怎么办呢？
凉拌炒鸡蛋，别做了吧。
经过许久的思考，我们可以修改定义：
令 dp[x] 表示从 x 号节点出发，x 子树中所有子节点第一次被访问到的时间减去 x 号节点第一次被访问的时间的和。说人话，就是假设 x 号节点第一次被访问的时间为 0，就可以直接按照之前的想法求子树和，之后状态转移的时候再处理。
状态转移方程的推导
假设第 x 号节点存在子节点 y_1,y_2\dots y_k，siz[x] 表示 x 的子树大小（包括 x 本身），从编号小的结点遍历到编号大的节点。
我们以存在 2 个子节点的子树为例，稍加推理则有：
\textstyle dp[x]=dp[y_1]+siz[y_1]\times 1 +dp[y_2]+siz[y_2]\times (1+2\times siz[y_1])
这个式子看着难懂，其实一点也不简单。
对于子节点 y_1，假设 dp[y_1] 已知（利用深搜思想）。那么回顾定义，在这一步的分析中，y_1 号节点第一次被访问的时间是 1 (假设访问 x 号节点的时间为 0)，可是在计算 dp[y_1] 的时候我们认为访问 y_1 节点的时间为 0。那么 y_1 子树上所有节点对此时答案的贡献也都要增加 1 （总共增加 siz[y_1]\times 1），最终 y_1 号子树对答案的贡献是 dp[y_1]+siz[y_1] \times 1。同理，因为我们需要访问完 y_1 号子树后所有节点后回到 x 节点（用时为 2\times siz[y_1]），之后再访问 y_2 号节点，所以访问到 y_2 号节点的时间应该是 1+2\times siz[y_1]，最终 y_2 号节点对答案的贡献是 dp[y_2]+siz[y_2]\times (1+2\times siz[y_1])。于是我们便有了上面这个特殊的状态转移方程。
紧接着，利用特殊到一般的思想，我们获得了一个正确的状态转移方程。建议尝试自己推理一下：当第 x 号节点存在子节点 y_1,y_2\dots y_k 时，有：
\textstyle dp[x]=\sum_{i=1}^{k}(dp[y_i]+siz[y_i]\times (1+2\times \sum_{j=1}^{j<i}siz[y_j]) )
此时我们已经完成了假设以 1 号节点为根节点和起点时的任务(时间复杂度 O(n\log{n})），并且证明了无论遍历顺序如何都不会影响答案，在这种假设下，一个深搜即可解决问题，最终答案为 dp[1]。但是为了这道题后续需要的操作，我们将这个式子进行化简。建议尝试自己推理一下：
\begin{aligned}\textstyle dp[x]&=\sum_{i=1}^{k}(dp[y_i]+siz[y_i]\times (1+2\times \sum_{j=1}^{j<i}siz[y_j]) )\\\textstyle &=\sum_{i=1}^{k}dp[y_i]+\sum_{i=1}^{k}siz[y_i]+2\times \sum_{i=1}^{k}\sum_{j=1}^{j<i}(siz[y_j]\times siz[y_i])\\\textstyle &=\sum_{i=1}^{k}dp[y_i]+\sum_{i=1}^{k}siz[y_i]+(\sum_{i=1}^{k}siz[y_i])^2-\sum_{i=1}^{k}siz[y_i]^2\\\textstyle &=\sum_{i=1}^{k}dp[y_i]+(siz[x]-1)+(siz[x]-1)^2-\sum_{i=1}^{k}siz[y_i]^2\\\textstyle &=\sum_{i=1}^{k}dp[y_i]+siz[x]^2-siz[x]-\sum_{i=1}^{k}siz[y_i]^2\end{aligned}
其中有一个东西我在这里解释一下：关于 2\times \sum_{i=1}^{k}\sum_{j=1}^{j<i}(siz[y_j]\times siz[y_i]) 是如何变为 (\sum_{i=1}^{k}siz[y_i])^2-\sum_{i=1}^{k}siz[y_i]^2 的。
我们举个例子：假设 k=3，那么则有：
\textstyle \sum_{i=1}^{k=3}\sum_{j=1}^{j<i}(siz[y_j]\times siz[y_i])=siz[y_1]\times siz[y_2]+siz[y_1]\times siz[y_3]+siz[y_2]\times siz[y_3]
我们都学过 (a+b+c)^2=(a^2+b^2+c^2)+2ab+2bc+2ac，所以有：
\begin{aligned}\textstyle \sum_{i=1}^{k=3}\sum_{j=1}^{j<i}(siz[y_j]\times siz[y_i])&=siz[y_1]\times siz[y_2]+siz[y_1]\times siz[y_3]+siz[y_2]\times siz[y_3]\\&=\frac{(\sum_{i=1}^{k=3}siz[y_i])^2-\sum_{i=1}^{k=3}siz[y_i]^2}{2}\end{aligned}
最终状态转移：
$$
\textstyle dp[x]=\sum_{i=1}^{k}dp[y_i]+siz[x]^2-siz[x]-\sum_{i=1}^{k}siz[y_i]^2
$$
### 正解思路
在之前的思路里，我们假设了 $1$ 号节点为出发节点。可题意中起始节点不确定。这时候考虑**换根 DP**。
令 $ans[x]$ 表示以 $x$ 为起始节点和根节点的答案。
接着考虑计算 $x$ 号节点的所有子节点的答案。显然，对于 $x$ 号节点的所有子节点 $z$，我们只要将 $dp[x]$ 中 $z$ 节点的贡献扣除，再在 $dp[z]$ 中加入 $x$ 节点的贡献，就可以计算出以 $z$ 为起始节点的答案。这里主要涉及状态的转移推理。**建议尝试自己推理一下**，我会将重点步骤列出，最终可以根据结论编写代码。
在换根前，有：
$$
\textstyle ans[x]=dp[x]
$$
因为 $x$ 为根节点，所以有：
$$
\begin{aligned}
\textstyle dp[x]&=\sum_{i=1}^{k}dp[y_i]+siz[x]^2-siz[x]-\sum_{i=1}^{k}siz[y_i]^2
\\
&=\sum_{i=1}^{k}dp[y_i]+n^2-n-\sum_{i=1}^{k}siz[y_i]^2
\end{aligned}
$$
所以：
$$
\textstyle ans[x]=\sum_{i=1}^{k}dp[y_i]+n^2-n-\sum_{i=1}^{k}siz[y_i]^2
$$
换根后，令 $newdp[x]$ 表示扣除了 $z$ 的贡献后的答案（即 $x$ 号节点的子树中不包含 $z$），与原状态转移方程对应计算，则有：
$$
\textstyle siz[x]=n-siz[z]
$$
以及：
$$
\textstyle newdp[x]=ans[x]-dp[z]-(n^2-n)+siz[x]^2-siz[x]+siz[z]^2
$$
此时在 $dp[z]$ 中加入 $x$ 节点的贡献，与原状态转移方程对应计算，最终的状态转移方程如下：
$$
\begin{aligned}\textstyle ans[z]&=dp[z]+newdp[x]-siz[z]^2+n^2+siz[z]-n-(n-siz[z])^2\\&=ans[x]-n+2\times siz[z]\end{aligned}
$$
将 $newdp[x]$ 的式子代入表示，最终得到：
$$
\textstyle ans[z]=ans[x]-n+2\times siz[z]
$$
推了这么久，最终式子竟然如此简单！(打代码的时候狂喜）。
## Coding思路总结
首先，假设 $1$ 号节点为根节点，利用**树形 DP** 的思想将以 $1$ 号节点为起始节点的答案计算出来。
状态转移：
$$
\textstyle dp[x]=\sum_{i=1}^{k}dp[y_i]+siz[x]^2-siz[x]-\sum_{i=1}^{k}siz[y_i]^2
$$
接着使用**换根 DP**，将不同节点为起始节点和根节点的答案一并算出。
状态转移：
$$
\textstyle ans[z]=ans[x]-n+2\times siz[z]
$$
## AC Code
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,u,v,sz[N],dp[N],ans[N],mn;
vector<int>vc[N];
int dfs1(int x,int fa)
{
for(auto i:vc[x])//枚举子节点
{
if(i==fa)continue;
dp[i]=dfs1(i,x);//先计算子节点的答案
sz[x]+=sz[i];//顺便计算siz数组
dp[x]+=dp[i]-(sz[i]*sz[i]);//依照状态转移方程更新dp
}
dp[x]+=sz[x]*sz[x]-sz[x];//依照状态转移方程更新dp
return dp[x];
}
void dfs2(int x,int fa)
{
for(auto i:vc[x])//枚举子节点
{
if(i==fa)continue;
ans[i]=ans[x]-n+2*sz[i];//依照状态转移方程更新ans
mn=min(mn,ans[i]);
dfs2(i,x);
}
}
signed main()
{
cin>>n;
for(int i=1;i<n;i++)
{
cin>>u>>v;
vc[u].push_back(v);
vc[v].push_back(u);
}
for(int i=1;i<=n;i++)sz[i]=1;//将自己计入siz数组
mn=ans[1]=dfs1(1,0);//先尝试以1为根节点树形dp
dfs2(1,0);//接着换根计算答案
cout<<mn;
return 0;
}
```
写了快 2 个小时的题解。