树的重心和中心
树的中心
定义
树上任意一条直径所在的链的中点，当直径为偶数的时候，中心由一个点
(
u
)
(u)
(
u
)
构成。当直径为奇数的时候，中心由两个点构成
(
u
,
v
)
(u,v)
(
u
,
v
)
。
性质
- 树的中心是唯一的，有一个且仅有一个中心
-
树上任意一个节点
uu
u
到另外一个任意节点
vv
v
的的距离是最大值，那么
vv
v
为树上直径两个端点的其中一个。
例题
如何寻找树的中心，定义函数
F
a
r
(
x
)
=
y
Far(x)=y
F
a
r
(
x
)
=
y
为节点
x
x
x
到所有节点的最远节点
y
y
y
。
首先，我们任意指定一个节点
k
k
k
，求得
A
=
F
a
r
(
k
)
A=Far(k)
A
=
F
a
r
(
k
)
，则
A
A
A
为直径的一个端点，然后我们求得
B
=
F
a
r
(
A
)
B=Far(A)
B
=
F
a
r
(
A
)
，那么节点
A
B
AB
A
B
和其唯一的一条路径将是这颗树的一个直径。
对树进行中心分解，分解得到几个连通分量，计算连通分量的路径最长的节点数，计算答案。
struct Edge
{
int to;
int nxt;
} e[400005];
int head[200005];
int tot;
void add(int u, int v)
{
tot++;
e[tot].to = v;
e[tot].nxt = head[u];
head[u] = tot;
}
pii far(int u, int r)
{
pii ans = make_pair(0, u);
for (int ne = head[u]; ne; ne = e[ne].nxt)
{
int to = e[ne].to;
if (to == r)
continue;
pii sub = far(to, u);
if (sub.first + 1 > ans.first)
ans = make_pair(sub.first + 1, sub.second);
}
return ans;
}
void pTravel(int u, int r, int end, vector<int> &path)
{
path.push_back(u);
if (u == end)
return;
for (int ne = head[u]; ne; ne = e[ne].nxt)
{
int to = e[ne].to;
if (to == r)
continue;
pTravel(to, u, end, path);
if (!path.empty() && path.back() == end)
return;
}
path.pop_back();
}
int eCnt(int u, int r, int len)
{
if (len == 0)
return 1;
int ans = 0;
for (int ne = head[u]; ne; ne = e[ne].nxt)
{
int to = e[ne].to;
if (to == r)
continue;
ans += eCnt(to, u, len - 1);
}
return ans;
}
int main()
{
FR;
int n;
cin >> n;
for (int i = 0; i < n - 1; i++)
{
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
pii a = far(1, 1);
pii b = far(a.second, a.second);
int dim = b.first;
int EA = a.second;
int EB = b.second;
vector<int> mpath;
pTravel(EA, EA, EB, mpath);
if (dim & 1)
{
int MA = mpath[(dim - 1) / 2];
int MB = mpath[(dim + 1) / 2];
ll CA = eCnt(MA, MB, (dim - 1) / 2);
ll CB = eCnt(MB, MA, (dim - 1) / 2);
ll ans = (CA * CB) % MOD353;
cout << ans;
}
else
{
int M = mpath[dim / 2];
ll ans = 1;
ll psum = 0;
for (int ne = head[M]; ne; ne = e[ne].nxt)
{
ll cnt = eCnt(e[ne].to, M, dim / 2 - 1);
ans = (ans + (ans * cnt) % MOD353) % MOD353;
psum = (psum + cnt) % MOD353;
}
cout << ((ans - psum - 1) % MOD353 + MOD353) % MOD353;
}
return 0;
}
树的重心
定义
树上的每一个节点都有一个平衡值，该平衡值的定义为，以该节点为根节点，所有子树中节点数量最大的那个子树中节点数量。
树的重心是树上的一个节点，其平衡值是树中节点中最小的那个。
性质
- 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
- 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
- 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
- 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
例题
对整棵树进行DFS，模仿树链剖分，但是值得注意的是，不要忘了
向上的子树
。
#include <algorithm>
#include <cstdio>
using namespace std;
#define FR freopen("in.txt", "r", stdin)
#define FW freopen("out.txt", "w", stdout)
typedef long long ll;
struct Edge
{
int to;
int nxt;
} e[40005];
int head[20005];
int tot = 0;
inline void add(int u, int v)
{
tot++;
e[tot].to = v;
e[tot].nxt = head[u];
head[u] = tot;
}
int ssize[20005];
int weight[20005];
int n;
int ans = 0;
int cnt = 0;
void dfs(int u, int r)
{
ssize[u] = 1;
for (int ne = head[u]; ne != 0; ne = e[ne].nxt)
{
int v = e[ne].to;
if (v != r)
{
dfs(v, u);
ssize[u] += ssize[v];
weight[u] = max(weight[u], ssize[v]);
}
}
weight[u] = max(weight[u], n - ssize[u]);
if (weight[u] <= n / 2)
{
if (ans == 0 || u < ans)
{
ans = u;
cnt = weight[u];
}
}
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
head[i] = 0;
ssize[i] = 0;
weight[i] = 0;
}
tot = 0;
ans = 0;
cnt = 0;
for (int i = 0; i < n - 1; i++)
{
int u, v;
scanf("%d %d", &u, &v);
add(u, v);
add(v, u);
}
dfs(1, 1);
printf("%d %d\n", ans, cnt);
}
return 0;
}