【題目鏈接】

洛谷 P3478 [POI 2008] STA-Station

【題目考點】

1. 樹形動規：換根動規

換根動規，又名二次掃描法，一般是給一顆不定根樹，通過兩次掃描來求解。
我們可以先任選一個根結點root，通過樹形動規的思想計算出一個答案。再考慮當root的子結點作為根結點時，答案的變化。
換根動規的三個步驟:

1. 指定某個結點為根結點root。
2. 第一次搜索完成預處理，得到以root為根的解。孩子=>根。
3. 第二次搜索進行換根動規，由已知解的結點推出相鄰結點的解。根=>孩子。

【解題思路】

設$dp$數組，$d{p}_u$表示以結點u為整棵樹的根時所有結點的深度之和，在無權圖中，就是所有結點到根結點的路徑長度之和。
$si{z}_u$表示在有根樹中以u為根的子樹的結點數量。
先將結點1設為整棵樹的根結點，進行第一趟dfs，深搜時可知訪問到的結點的深度，將深度加和保存在$d{p}_1$。與此同時可以求出$siz$數組，即以結點1為根的有根樹中每個子樹的結點數。
接下來第二趟dfs，進行換根動規。dfs從結點u訪問到鄰接點v時，就嘗試將整棵樹的根從結點u轉移到結點v，考察轉移后所有結點到整棵樹根結點的路徑加和的變化。
以v為根的子樹中的結點從考慮到結點u的路徑轉變為考慮到結點v的路徑，每條路徑長度減少1，共有$si{z}_v$個結點到根結點的路徑長度減少，總減少長度為$si{z}_v$。
v的上方子樹（除去以v為根的子樹外其它結點構成的子樹）的結點數為$n?si{z}_v$，從考慮這些結點到結點u的路徑轉為考慮這些結點到結點v的路徑，每條路徑長度增加1，總增加長度為$n?si{z}_v$。
因此以結點v為整棵樹根結點時，所有結點到v的路徑長度加和即所有結點的深度加和為$d{p}_v=d{p}_u?si{z}_v+n?si{z}_v$。這是從雙親到孩子的轉移，因此該狀態轉移方程應該寫在調用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;
}