【题目链接】
洛谷 P3478 [POI 2008] STA-Station
【题目考点】
1. 树形动规:换根动规
换根动规,又名二次扫描法,一般是给一颗不定根树,通过两次扫描来求解。
我们可以先任选一个根结点root,通过树形动规的思想计算出一个答案。再考虑当root的子结点作为根结点时,答案的变化。
换根动规的三个步骤:
- 指定某个结点为根结点root。
- 第一次搜索完成预处理,得到以root为根的解。孩子=>根。
- 第二次搜索进行换根动规,由已知解的结点推出相邻结点的解。根=>孩子。
【解题思路】
设dpdpdp数组,dpudp_udpu表示以结点u为整棵树的根时所有结点的深度之和,在无权图中,就是所有结点到根结点的路径长度之和。
sizusiz_usizu表示在有根树中以u为根的子树的结点数量。
先将结点1设为整棵树的根结点,进行第一趟dfs,深搜时可知访问到的结点的深度,将深度加和保存在dp1dp_1dp1。与此同时可以求出sizsizsiz数组,即以结点1为根的有根树中每个子树的结点数。
接下来第二趟dfs,进行换根动规。dfs从结点u访问到邻接点v时,就尝试将整棵树的根从结点u转移到结点v,考察转移后所有结点到整棵树根结点的路径加和的变化。
以v为根的子树中的结点从考虑到结点u的路径转变为考虑到结点v的路径,每条路径长度减少1,共有sizvsiz_vsizv个结点到根结点的路径长度减少,总减少长度为sizvsiz_vsizv。
v的上方子树(除去以v为根的子树外其它结点构成的子树)的结点数为n−sizvn-siz_vn−sizv,从考虑这些结点到结点u的路径转为考虑这些结点到结点v的路径,每条路径长度增加1,总增加长度为n−sizvn-siz_vn−sizv。
因此以结点v为整棵树根结点时,所有结点到v的路径长度加和即所有结点的深度加和为dpv=dpu−sizv+n−sizvdp_v = dp_u-siz_v+n-siz_vdpv=dpu−sizv+n−sizv。这是从双亲到孩子的转移,因此该状态转移方程应该写在调用dfs从孩子开始搜索的语句之前。
最后求出dp数组大值的下标,即为本题的结果。求最大值下标的过程可以在dfs的过程中进行。
【题解代码】
解法1:树形动规 换根动规
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
int n, dep[N], siz[N], mxi = 1;
vector<int> edge[N];
long long dp[N];//dp[u]:整棵树以u为根时所有结点的深度之和
void dfs1(int u, int fa, int dep)
{dp[1] += dep;siz[u] = 1;for(int v : edge[u]) if(v != fa){dfs1(v, u, dep+1);siz[u] += siz[v];}
}
void dfs2(int u, int fa)
{for(int v : edge[u]) if(v != fa){dp[v] = dp[u]-siz[v]+n-siz[v];dfs2(v, u);}if(dp[u] > dp[mxi])mxi = u;
}
int main()
{int u, v;cin >> n;for(int i = 1; i < n; ++i){cin >> u >> v;edge[u].push_back(v);edge[v].push_back(u);}dfs1(1, 0, 0);dfs2(1, 0);cout << mxi;return 0;
}