【題目鏈接】

洛谷 P1395 會議

【題目考點】

1. 樹形動規：樹的重心

本題為求樹的重心模板題

【解題思路】

樹的重心：相比于樹中其它結點，其所有的子樹中結點數最多的子樹的結點數最少，該結點就是這棵樹的重心。
另一種定義：
結點的平衡值為以該結點為根的樹的所有子樹中結點數最多的子樹的結點數。樹的重心為平衡值最小的結點。

樹中所有點到某個點的距離和中，到重心的距離和是最小的。
見樹的重心相關證明

首先對無根樹進行dfs，得到有根樹，求出有根樹中以每個結點為根的子樹的結點數，該過程也是一個樹形動規的過程。
狀態定義：$si{z}_u$表示以結點u為根的子樹的大小，即以結點u為根的子樹的結點數量。
狀態轉移方程：以u為根的子樹的大小為所有以u的孩子v為根的子樹的大小加和，再加上1（結點u）。
$si{z}_u=\sum si{z}_v+1，v\in chil{d}_u$，$chil{d}_u$表示u的子結點構成的集合。

求出$siz$數組的同時，可以求樹的重心。

狀態定義：$d{p}_u$：結點u的平衡值。即結點u的所有子樹最大的子樹的大小。
狀態轉移方程：
無根樹中結點u的子樹，包括有根樹中結點u的子樹，以及結點u的“上方子樹”。
上方子樹指的是有根樹中除了以u為根的子樹外所有結點構成的子樹，該上方子樹的大小為$n?si{z}_u$。
因此dpu=max?{{sizv},n?sizu},v∈childudp_u = \max\{\{{siz_v}\}, n-siz_u\}, v\in child_udpu?=max{{sizv?},n?sizu?},v∈childu?

具體實現時，對樹做dfs的過程中完成狀態轉移。嘗試訪問結點u的每個孩子，從結點u訪問到孩子v時，先進行dfs(v)，搜索求出$si{z}_v$與$d{p}_v$，而后根據$si{z}_v$更新$si{z}_u$與$d{p}_u$。
在訪問結點u的所有孩子后，再使用$n?si{z}_u$更新$d{p}_u$。
dfs結束求出$dp$數組。樹的重心為平衡值最小的結點，那么求$dp$數組最小值的下標，即為樹的重心cent。
本題還要求求出所有結點到重心的距離和，該過程可以使用樹形動規完成、也可以使用深搜完成。
如果使用樹形動規完成：
以重心cent為根進行深搜：
狀態定義：$di{s}_u$，有根樹中以u為根的子樹中所有結點到u的距離加和。
狀態轉移方程：設v是u的一個孩子，那么v中所有結點到u的距離加和，為v中所有結點到v的距離加和$di{s}_v$。以v為根的子樹中所有結點要想到達u，還要經過邊(u,v)，邊權為1。以v為根的子樹共有$si{z}_v$個結點，因此總路徑加和增加了$si{z}_v$。注意：由于整棵樹的根發生了改變，因此要重新求$siz$數組。
所有結點到重心的路徑加和為$di{s}_{cent}$

【題解代碼】

解法1：樹形動規 求樹的重心。樹形動規求路徑加和。

#include <bits/stdc++.h>
using namespace std;
#define N 50005
int n, siz[N], dp[N], dis[N];//siz[u]：以u為根的樹的結點數（的大小） dp[u]:以u為整棵樹的根時最大子樹的大小 
vector<int> edge[N];
void dfs(int u, int fa)
{siz[u] = 1;for(int v : edge[u]) if(v != fa){dfs(v, u);siz[u] += siz[v];dp[u] = max(dp[u], siz[v]);}dp[u] = max(dp[u], n-siz[u]);
}
void dfs2(int u, int fa)
{siz[u] = 1;for(int v : edge[u]) if(v != fa){dfs2(v, u);siz[u] += siz[v];dis[u] += dis[v]+siz[v];}
}
int main()
{int a, b, cent = 1;cin >> n;for(int i = 1; i < n; ++i){cin >> a >> b;edge[a].push_back(b);edge[b].push_back(a);	}dfs(1, 0);for(int i = 1; i <= n; ++i)if(dp[i] < dp[cent])cent = i;dfs2(cent, 0);cout << cent << ' ' << dis[cent]; return 0;
}

解法2：樹形動規 求樹的重心。深搜求路徑加和。

#include <bits/stdc++.h>
using namespace std;
#define N 50005
int n, siz[N], dp[N], ans;//siz[u]：以u為根的樹的結點數（的大小） dp[u]:以u為整棵樹的根時最大子樹的大小 
vector<int> edge[N];
void dfs(int u, int fa)
{siz[u] = 1;for(int v : edge[u]) if(v != fa){dfs(v, u);siz[u] += siz[v];dp[u] = max(dp[u], siz[v]);}dp[u] = max(dp[u], n-siz[u]);
}
void dfs2(int u, int fa, int len)//len：根到u的路徑長度 
{ans += len;for(int v : edge[u]) if(v != fa)dfs2(v, u, len+1);
}
int main()
{int a, b, cent = 1;cin >> n;for(int i = 1; i < n; ++i){cin >> a >> b;edge[a].push_back(b);edge[b].push_back(a);	}dfs(1, 0);for(int i = 1; i <= n; ++i)if(dp[i] < dp[cent])cent = i;dfs2(cent, 0, 0);cout << cent << ' ' << ans; return 0;
}