|
|
## 一、树的直径
|
|
|
|
|
|
记录最长、次长，输出 $max(最长+次长)$
|
|
|
|
|
|
#### [$AcWing$ $1072$ 树的最长路径](https://www.cnblogs.com/littlehb/p/15784687.html)
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 10010, M = N << 1;
|
|
|
int n; // n个结点
|
|
|
|
|
|
// 链式前向星
|
|
|
int h[N], e[M], w[M], ne[M], idx;
|
|
|
void add(int a, int b, int c) {
|
|
|
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
int ans; // 答案,直径
|
|
|
int mx1[N], mx2[N]; // mx1[i],mx2[i]:经过i点的最长,次长长度是多少
|
|
|
|
|
|
void dfs(int u, int fa) {
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (v == fa) continue; // v点访问过了
|
|
|
|
|
|
// 走v子树,完成后，v子树中每个节点的mx1[v],mx2[v]都已经准备好，u节点可以直接利用
|
|
|
dfs(v, u);
|
|
|
|
|
|
// w[i]:u->v的路径长度,mx1[u]:最长路径,mx2[u]:次长路径
|
|
|
int x = mx1[v] + w[i];
|
|
|
if (mx1[u] <= x) // v可以用来更新u的最大值
|
|
|
mx2[u] = mx1[u], mx1[u] = x; // 最长路转移
|
|
|
else if (mx2[u] < x)
|
|
|
mx2[u] = x; // 次长路转移
|
|
|
}
|
|
|
// 更新结果
|
|
|
ans = max(ans, mx1[u] + mx2[u]);
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
cin >> n;
|
|
|
memset(h, -1, sizeof h); // 初始化邻接表
|
|
|
for (int i = 1; i < n; i++) { // n-1条边
|
|
|
int a, b, c;
|
|
|
cin >> a >> b >> c;
|
|
|
add(a, b, c), add(b, a, c); // 换根dp一般用于无向图
|
|
|
}
|
|
|
dfs(1, 0); // 任选一个点作为根节点,此处选择的是肯定存在的1号结点
|
|
|
cout << ans << endl;
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
```
|
|
|
|
|
|
## 二、树的中心
|
|
|
#### [$AcWing$ $1073$. 树的中心](https://www.cnblogs.com/littlehb/p/15786805.html)
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 10010, M = N << 1;
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
|
|
|
int n; // n个节点
|
|
|
int mx1[N]; // mx1[u]：u节点向下走的最长路径的长度
|
|
|
int mx2[N]; // mx2[u]：u节点向下走的次长路径的长度
|
|
|
int id[N]; // id[u]：u节点向下走的最长路径是从哪一个节点下去的
|
|
|
int up[N]; // up[u]：u节点向上走的最长路径的长度
|
|
|
|
|
|
// 邻接表
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
void add(int a, int b, int c = 0) {
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
// 功能:以u为根，向叶子进行递归，利用子节点返回的最长信息，更新自己的最长和次长,并记录最长是从哪个节点来的
|
|
|
void dfs1(int u, int fa) {
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (v == fa) continue;
|
|
|
|
|
|
// 递归完才能有数据
|
|
|
dfs1(v, u);
|
|
|
int x = mx1[v] + w[i]; // u问到：儿子v可以带我走多远？
|
|
|
if (mx1[u] < x) { // 更新最长
|
|
|
mx2[u] = mx1[u]; // ① 更新次长
|
|
|
mx1[u] = x; // ② 更新最长
|
|
|
id[u] = v; // ③ 记录最长来源
|
|
|
} else if (mx2[u] < x) // 更新次长
|
|
|
mx2[u] = x;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// 功能：完成向上的信息填充
|
|
|
void dfs2(int u, int fa) {
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (v == fa) continue;
|
|
|
// 二者取其一
|
|
|
if (id[u] == v)
|
|
|
up[v] = max(mx2[u], up[u]) + w[i];
|
|
|
else
|
|
|
up[v] = max(mx1[u], up[u]) + w[i];
|
|
|
// 递归
|
|
|
dfs2(v, u);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
memset(h, -1, sizeof h);
|
|
|
cin >> n;
|
|
|
for (int i = 1; i < n; i++) {
|
|
|
int a, b, c;
|
|
|
cin >> a >> b >> c;
|
|
|
add(a, b, c), add(b, a, c);
|
|
|
}
|
|
|
dfs1(1, 0); // 选择任意一个节点进行dfs,用儿子更新父亲的统计信息
|
|
|
dfs2(1, 0); // 向上
|
|
|
|
|
|
int res = INF;
|
|
|
for (int i = 1; i <= n; i++) res = min(res, max(mx1[i], up[i]));
|
|
|
printf("%d\n", res);
|
|
|
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
```
|
|
|
|
|
|
## 三、树的重心
|
|
|
|
|
|
#### [$CF1406C$. $Link$ $Cut$ $Centroids$](https://codeforces.com/contest/1406/problem/C)
|
|
|
> **账号**：$10402852@qq.com$ **密码**：$m****2$
|
|
|
> **关键词**：**求树的重心**
|
|
|
|
|
|
|
|
|
**题目大意**
|
|
|
给你一棵树的结点数$n$和$n-1$条边，你可以删除一条边再增加一条边，使得树的重心唯一,输出这条边
|
|
|
> **注意**：有$Specail$ $Judge$，如果删除哪条都行，那就随意删除一条就行
|
|
|
|
|
|
**告诉你的已知性质**：
|
|
|
① 删除重心后所得的所有子树，节点数不超过原树的$1/2$，**一棵树最多有两个重心**
|
|
|
② 树中所有节点到重心的距离之和最小，如果有两个重心，那么他们距离之和相等
|
|
|
③ 两个树通过一条边合并，新的重心在原树两个重心的路径上
|
|
|
④ 树删除或添加一个叶子节点，重心最多只移动一条边
|
|
|
⑤ 一棵树最多有两个重心，且相邻
|
|
|
|
|
|
|
|
|
树的重心定义为树的某个节点，当去掉该节点后，树的各个连通分量中，节点数最多的连通分量其节点数达到最小值。树可能存在多个重心。如下图,当去掉点$1$后，树将分成两个连通块：$(2,4,5)，(3,6,7)$，则最大的连通块包含节点个数为$3$。若去掉点$2$，则树将分成$3$个部分，$(4)，(5)，(1,3,6,7)$最大的连通块包含$4$个节点；第一种方法可以 **得到更小的最大联通分量**。可以发现，其他方案不可能得到比$3$更小的值了。所以，点$1$是树的重心。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
**思路**
|
|
|
- 如果找到只有一个重心，那么直接删一个重心的直连边然后加回去就好
|
|
|
- 如果找到两个重心，那么在其中一个重心上找到一个直连点不是另一个重心，删除连另外一个就好
|
|
|
|
|
|
**如何求树的重心？**
|
|
|
|
|
|
1、先任选一个结点作为根节点(比如$1$号节点)，把无根树变成有根树。然后设$sz[i]$表示以$i$为根节点的子树节点个数。转移方程为$\displaystyle sz[u]=\sum_{son[u]=v} (sz[v])$
|
|
|
|
|
|
2、设$son[i]$表示删去节点$u$后剩下的连通分量中最大子树节点个数。其中一部分在原来$i$其为根的子树。
|
|
|
$$son[i]=\max_{\substack{j \in son[i]}}(son[i],sz[j])$$
|
|
|
|
|
|
另外一部分在$i$的 **上方** 子树有$n-sz[i]$个。
|
|
|
$$son[i]=max(son[i],n-sz[i])$$
|
|
|
|
|
|
|
|
|
|
|
|
3、利用重心性质： ① 树必须存在$1$或$2$个重心 , ② 如果某个点是重心，那么把它拿下后，其它连通块的个数都需要小于等于整棵树节点个数的一半。 满足条件 ② 的结点数量不会超过$2$个！分别记录为$r_1,r_2$。
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
const int N = 1e5 + 10, M = N << 1;
|
|
|
#define int long long
|
|
|
#define endl "\n"
|
|
|
|
|
|
// 链式前向星
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
void add(int a, int b, int c = 0) {
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
int sz[N]; // sz[i]:以i为根的子树中节点个数
|
|
|
int son[N]; // son[i]:去掉节点i后，剩下的连通分量中最大子树节点个数
|
|
|
int r1, r2, n;
|
|
|
|
|
|
void dfs(int u, int fa) {
|
|
|
sz[u] = 1; // u为根的子树中，最起码有一个节点u
|
|
|
son[u] = 0; // 把节点u去掉后，剩下的连通分量中最大子树节点个数现在还不知道，预求最大，先设最小
|
|
|
|
|
|
for (int i = h[u]; ~i; i = ne[i]) { // 枚举u的每一条出边
|
|
|
int v = e[i];
|
|
|
if (v == fa) continue;
|
|
|
dfs(v, u); // 先把v为根的子树遍历完
|
|
|
sz[u] += sz[v]; // 把 v中获取填充的sz[v]值，用于组装自己sz[u]
|
|
|
son[u] = max(son[u], sz[v]); // 如果把u节点去掉，那么它的所有子节点v为根的子树中节点数，可以参加评选：
|
|
|
// 评选的标准是：son[i]:去掉节点i后，剩下的连通分量中最大子树节点个数
|
|
|
}
|
|
|
son[u] = max(son[u], n - sz[u]); // 右上角的那一块也可能成为评选的获胜者
|
|
|
if ((son[u] << 1) <= n) r2 = r1, r1 = u; // 删除重心后所得的所有子树，节点数不超过原树的1/2，一棵树最多有两个重心
|
|
|
// 如果模拟u被删除后，得到的所有子树中节点数量最多的没有超过原树的1/2,那么这个r1=u表示：找到了一个重心u
|
|
|
// r2=r1表示：如果找到两个重心，那么r1,r2 一人一个，此时，r1中肯定有值，但 r2不一定有值
|
|
|
}
|
|
|
|
|
|
signed main() {
|
|
|
int T;
|
|
|
cin >> T;
|
|
|
while (T--) {
|
|
|
cin >> n;
|
|
|
// 多组测试数据，清空
|
|
|
memset(sz, 0, sizeof sz);
|
|
|
memset(son, 0, sizeof son);
|
|
|
// 初始化链式前向星
|
|
|
memset(h, -1, sizeof h);
|
|
|
idx = 0;
|
|
|
|
|
|
r1 = r2 = 0; // 重心清零
|
|
|
for (int i = 1; i < n; i++) { // n-1条边
|
|
|
int x, y;
|
|
|
cin >> x >> y;
|
|
|
add(x, y), add(y, x);
|
|
|
}
|
|
|
dfs(1, 0); // 以1号点为入口，它的父节点是0
|
|
|
|
|
|
if (r2 == 0) { // 如果只有一个重心，r2=0表示没有第二个重心
|
|
|
int u = r1, v = e[h[u]];
|
|
|
cout << u << " " << v << endl; // 切掉一条边u->v
|
|
|
cout << u << " " << v << endl; // 加一条边 u->v
|
|
|
} else { // 如果有两个重心
|
|
|
int u = r2, v;
|
|
|
for (int i = h[u]; ~i; i = ne[i]) { // 不要删除掉两个重心相连接的那条边
|
|
|
v = e[i];
|
|
|
if (v != r1) break; // 只要对方节点不是另一个重心，那么就是可以删除的
|
|
|
}
|
|
|
cout << u << " " << v << endl; // 切一条边u->v，第二个重心所在边需要被切掉
|
|
|
cout << v << " " << r1 << endl; // 加一条边v->r1,不走u了，走了u的一个子节点v
|
|
|
}
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
