思路：

基于樹形 DP 的兩次遍歷（第一次dfs計算以某個初始根（這里選了 1）為根時各子樹的深度和與節點數，第二次zy進行換根操作，更新每個節點作為根時的深度和）

換根原理：

更換主根，只需要對父節點進行運算即可，沒必要再次循環；后面代碼有詳解：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
long long n,d[N],p[N],o[N];//deep數組存儲以每個節點為根時的總深度和，point數組存儲子樹大小
vector<vector<int>> a; // 鄰接表存儲樹結構

// 第一次DFS：計算以節點1為根時，每個節點的子樹大小和子樹總深度
void dfs(int x,int pr){
? ? p[x]=1; // 初始化當前節點的子樹大小為1（僅包含自身）
? ? d[x]=0; // 初始化當前節點的子樹總深度為0
? ??
? ? // 遍歷當前節點的所有鄰接節點
? ? for(auto i:a[x]){
? ? ? ? if(i!=pr){ // 避免處理父節點（防止重復計算）
? ? ? ? ? ? dfs(i,x); // 遞歸處理子節點
? ? ? ? ? ??
? ? ? ? ? ? // 更新當前節點的子樹總深度：
? ? ? ? ? ? // d[i]是子節點i的子樹總深度，p[i]是子節點i的子樹大小
? ? ? ? ? ? // 每個子節點i的子樹中的所有節點到當前節點的距離都要+1，因此增加p[i]
? ? ? ? ? ? d[x]+=d[i]+p[i];
? ? ? ? ? ??
? ? ? ? ? ? // 更新當前節點的子樹大小：加上子節點i的子樹大小
? ? ? ? ? ? p[x]+=p[i];
? ? ? ? }
? ? } ? ?
}

// 第二次DFS：換根DP，計算以每個節點為根時的總深度和
void zy(int x,int pr){
? ? // 遍歷當前節點的所有鄰接節點
? ? for(auto i:a[x]){
? ? ? ? if(i!=pr){ // 避免處理父節點
? ? ? ? ? ? // 核心換根公式：
? ? ? ? ? ? // d[x]是以x為根的總深度和
? ? ? ? ? ? // n-p[i]是除了i的子樹外的節點數
? ? ? ? ? ? // p[i]是i的子樹大小
? ? ? ? ? ? // 當根從x變為i時，i的子樹中所有節點的深度減少1（距離根更近了）
? ? ? ? ? ? // 其余節點的深度增加1（距離根更遠了）
? ? ? ? ? ? d[i]=d[x]+n-p[i]-p[i];
? ? ? ? ? ??
? ? ? ? ? ? // 遞歸處理子節點，繼續換根過程
? ? ? ? ? ? zy(i,x);
? ? ? ? }
? ? }
}

int main(){
? ? cin>>n; // 輸入節點數
? ? a.resize(n + 1); // 調整鄰接表大小
? ??
? ? // 輸入n-1條邊，構建樹
? ? int m,l;?
? ? for(int i=1;i<n;i++){
? ? ? ? cin>>m>>l;
? ? ? ? a[m].push_back(l);
? ? ? ? a[l].push_back(m);
? ? }
? ??
? ? // 第一次DFS：以節點1為根，計算初始子樹信息
? ? dfs(1,0);
? ? // 第二次DFS：換根DP，計算每個節點作為根時的總深度和
? ? zy(1,0);
? ??
? ? // 尋找總深度和最大的節點
? ? int mi=n;
? ? for(int i=n-1;i>0;i--){
? ? ? ? if(d[i]>=d[mi])mi=i;
? ? }
? ??
? ? // 輸出結果
? ? cout<<mi<<endl;
? ??
? ? return 0;
}