树的重心
定义
对于树上每一个顶点,分别计算其所有子树中最大子树的顶点数,当此值最小时,这个顶点即为树的重心
。
性质
树的重心主要有一下性质:
- 以树的重心为根,每一子树的大小都不超过整棵树大小的一半。
- 树中所有顶点到重心的距离和比到其它顶点距离和小,若存在多个重心则到它们的距离一致。
- 若两棵树相连合成一颗新树,则新树的重心在原树两个重心的路径上。
- 在树上添加或删除一个叶子,树的重心最多移动到其邻居的位置上。
求解方法
通过深度优先搜索计算每一子树的大小并记录,由$|V_{upper}|=|V_{all}|-|V_{lower}|-1$及定义可求解出重心位置,时间复杂度$O(n)$。
参考代码
// Submit Link : https://vjudge.net/problem/POJ-1655
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int N = 2e4 + 1;
int t;
int n;
vector<int> G[N];
int upper[N], lower[N];
int weight[N];
bool vis[N];
int centroid;
int dfs(int x) {
bool has_nxt = false;
bool is_centroid = true;
for ( int i = 0; i < (int) G[x].size(); ++i ) {
int nxt = G[x][i];
if ( !vis[nxt] ) {
vis[nxt] = true;
has_nxt = true;
int cur_sub_tree = dfs(nxt);
if ( cur_sub_tree > n / 2 )
is_centroid = false;
lower[x] += cur_sub_tree;
weight[x] = max(weight[x], cur_sub_tree);
}
}
if ( !has_nxt ) {
upper[x] = n - 1;
weight[x] = n - 1;
return 1;
}
upper[x] = n - lower[x] - 1;
if ( upper[x] > n / 2 )
is_centroid = false;
weight[x] = max(weight[x], upper[x]);
if ( is_centroid )
centroid = x;
return lower[x] + 1;
}
int main() {
scanf("%d", &t);
while ( t-- ) {
scanf("%d", &n);
int u, v;
for ( int i = 1; i < n; ++i ) {
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(u);
printf("%d %d\n", centroid, weight[centroid]);
memset(vis, 0, sizeof vis);
memset(lower, 0, sizeof lower);
memset(upper, 0, sizeof upper);
memset(weight, 0, sizeof weight);
memset(G, 0, sizeof G);
}
return 0;
}
树的直径
定义
树上距离最远两点的距离即称为树的直径
。
性质
- 直径的两个端点一定是两个叶子。
- 距离树上任意顶点最远的顶点一定是直径的某个端点。
- 对于两颗树,若用一条边将其连接从而构成新树,其直径的两个端点一定为原树四个顶点中的其中两个。
- 若树存在多条直径,则其交点是这些直径的中点。
- 在树上添加一个叶子,最多会改变直径中的一个端点。
求解方法
以任意顶点为根,搜索距离其最远的顶点$u$,再从这个顶点出发寻找距离其最远的顶点$v$,$(u,v)$即为树的直径。若树存在多条直径,则只需分别求距离其最远顶点即可。
亦或记录每个节点向下,所能延伸的最远距离$d_{1}$,和次远距离$d_{2}$,那么树的直径就是所有$d_{1}+d_{2}$的最大值。
参考代码
// Submit Link : https://vjudge.net/problem/SPOJ-PT07Z
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 1;
vector<int> G[N];
int n, d;
int dfs(int u = 1, int p = -1) {
int d1 = 0, d2 = 0;
for (auto v : G[u]) {
if ( v == p )
continue;
int d = dfs(v, u) + 1;
if ( d > d1 )
d2 = d1, d1 = d;
else if ( d > d2 )
d2 = d;
}
d = max(d, d1 + d2);
return d1;
}
int main() {
scanf("%d", &n);
int u, v;
for ( int i = 1; i < n; ++i ) {
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs();
printf("%d\n", d);
}