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}$$

$k$ 取其他数时同理。自此，我们就分析完毕，可以进行下一步操作。

最终状态转移：

$$\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

#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 个小时的题解。