定义
性质
利用性质1求树的重心
我感觉这个代码有毒,想哭,每次都用代码二,不过代码思想都一样
x
using namespace std;
//dis[u]: 表示以u为根的总距离
int n, size[101];
int fa[101];
int to[201], head[101], ne[201], cnt = 1; // 链式前向星
// 加无向边
void add_edge(int a, int b) {
to[cnt] = b;
ne[cnt] = head[a];
head[a] = cnt++;
}
//求以每个节点为根节点挂的节点个数,包括自身
int dfs(const int& u, const int& f) {
fa[u] = f;
size[u] = 1; //w[i]存储i号节点自身节点数量
for (int i = head[u]; i; i = ne[i]) {
if (to[i] == f) continue; //下一个点不是父节点
size[u] += dfs(to[i], u);
}
return size[u];
}
int main() {
scanf("%d", &n); //输入节点个数
for (int i = 1; i <= n - 1; i++) { //输入n - 1条边
int a, b; //输入边的两端
scanf("%d %d", &a, &b);
add_edge(b, a), add_edge(a, b);
}
dfs(1, 0); //以1为根节点,求以每个节点为根节点的树的大小
for (int i = 1; i <= n; i++) printf("%d\n", size[i]);
int mi = 0x7fffffff, mi_nu;
for (int i = 1; i <= n; i++) { // 枚举每个节点为根节点
int tp = n - size[i]; // 计算以i为根节点的最大子树节点数
for (int j = head[i]; j; j = ne[j]) {
if (to[j] == fa[i]) continue;
tp = max(tp, size[to[j]]);// 计算最大子树节点数
}
// 计算以i为根节点的最大子树的结点数最小值,并记录根节点的编号
if (mi > tp) {
mi_nu = i;
mi = tp;
}
}
printf("最大子树的结点数最小值:%d,该节点编号:%d\n", mi, mi_nu);
return 0;
}
xxxxxxxxxx
using namespace std;
const int N = 1e5 + 10;
const int M = N << 1;
//dis[u]: 表示以u为根的总距离
int n;
int to[M], head[N], ne[M], cnt; // 链式前向星
// 加无向边
void add_edge(int a, int b) {
to[++cnt] = b;
ne[cnt] = head[a];
head[a] = cnt;
}
int size[N]; // size[i] = 统计以每个节点i为根节点的树的节点数量
bool vis[N]; // 标记数组
int ct = -1;
int ans = N; // 记录最大子树节点数量最小值
inline int dfs(int u) { // 计算以u为根的树的节点个数
size[u] = 1; // 自己本身就是一颗树
int res = 0; // 记录最大子树节点数量
vis[u] = true;
for (int i = head[u]; i; i = ne[i]) {
if (vis[to[i]]) continue;
size[to[i]] = dfs(to[i]); //计算以to[i]为根的树的节点个数
res = max(res, size[to[i]]); // 记录最大子树节点数量
size[u] += size[to[i]];
}
res = max(res, n - size[u]); // 记录最大子树节点数量
// ans = min(ans, res);
if (ans > res) { // 记录最大子树节点数量最小值
ans = res;
ct = u;
}
return size[u];
}
int main() {
scanf("%d", &n); //输入节点个数
for (int i = 1; i <= n - 1; i++) { //输入n - 1条边
int a, b; //输入边的两端
scanf("%d %d", &a, &b);
add_edge(b, a), add_edge(a, b);
}
dfs(1); // 以1为根节点进行搜索
for (int i = 1; i <= n ;i++) printf("size[%d] = %d\n", i, size[i]);
printf("%d %d\n", ct, ans);
return 0;
}
洛谷1364医院设置:https://www.luogu.com.cn/problem/P1364
题解:https://axieyun.top/posts/c91d.html
牛客网保卫村庄:[保卫村庄 (nowcoder.com)](https://ac.nowcoder.com/acm/problem/214212)
题解:https://axieyun.top/posts/8419.html0
定义
带权树上距离最远的两点
性质
1、直径两端点一点是叶子节点 2、距离任意点最远的点一定是直径的端点,这个基于贪心求直径方法的正确性可以得出 3、对于任意两棵树,如果第一棵树的直径两端点为(u,v),第二棵树直径的两端点为(x,y), 用一条边链接这两棵树,那么新树的直径一定是u,v,x,y,其中两个点。 4、若一棵树存在多条直径,那么这些直径交与一点且交点是这些直径的中点。 5、对于一棵树,如果在一个点的上接一个叶子节点,那么最多会改变直径的一个端点。
树的直径有两种求法
DFS利用性质二求解树的直径
、
xxxxxxxxxx
/*
方法:
随便把一个节点x当作根节点,从该节点出发,找到距离x最远的点l即为直径的一个端点;
再从l出发,找到距离l最远的点r,r即为直径的另一个端点。在第二遍dfs过程中,
我们可以记录这条直径的路径。
*/
using namespace std;
const int MAX_N = 1e5+5;
int n, ans, ex;
int l, r; // 直径两个端点
//链式前向星
int head[MAX_N], to[MAX_N << 1], nex[MAX_N << 1], v[MAX_N << 1], edge_cnt;
// 加边
void add_edge(int a, int b, int c) {
to[++edge_cnt] = b;
v[edge_cnt] = c;
nex[edge_cnt] = head[a];
head[a] = edge_cnt;
return ;
}
int pre[MAX_N];
// s记录从根节点走到now的距离,f为now的父节点
void dfs(const int& now, const int& s, const int& f) { //可以省略f,增加vis数组标记节点
if (s > ans) {
pre[now] = ex;
ans = s;
ex = now;
}
for (int i = head[now]; i; i = nex[i]) {
if (f == to[i]) continue; //防止往上搜
dfs(to[i], s + v[i], now);
}
return ;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n - 1; i++) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
add_edge(a, b, c);
add_edge(b, a, c);
}
dfs(1, 0, 0); //寻找距离1最远的点
//printf("ans = %d, ee = %d\n", ans, ex);
l = ex, ans = 0;
pre[l] = 0;
dfs(l, 0, 0); // 寻找距离l最远的点r
r = ex;
//printf("ans = %d, ee = %d\n", ans, ex);
printf("直径两端点:(%d,%d)\n", l, r);
printf("%d\n", ans); //直径长度
//输出直径路径
ex = r;
while (ex) {
printf("%d->", ex);
ex = pre[ex];
}
printf("0\n");
return 0;
}
树形DP
xxxxxxxxxx
using namespace std;
const int MAX_N = 1e5+5;
//d[i]记录i为根节点时,向下的最长距离;
// ans记录直径长度
int n, ans, d[MAX_N];
int l, r; // 直径两个端点
//链式前向星
int head[MAX_N], to[MAX_N << 1], nex[MAX_N << 1], v[MAX_N << 1], edge_cnt;
// 加边
void add_edge(int a, int b, int c) {
to[++edge_cnt] = b;
v[edge_cnt] = c;
nex[edge_cnt] = head[a];
head[a] = edge_cnt;
return ;
}
void dp(const int& x, const int& f) {
for (int i = head[x]; i; i = nex[i]) {
if (to[i] == f) continue;
dp(to[i], x); //递归到叶子节点 ,然后回溯回来
ans = max(ans, d[x] + d[to[i]] + v[i]); //跟新子直径长度
d[x] = max(d[x], d[to[i]] + v[i]); //维护
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n - 1; i++) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
add_edge(a, b, c);
add_edge(b, a, c);
}
dp(1, 0);
for (int i = 1; i <= n; i++) printf("d[%d] = %d\n", i, d[i]);
//printf("直径两端点:(%d,%d)\n", l, r);
printf("%d\n", ans); //直径长度
return 0;
}
xxxxxxxxxx
/*
思路:对于有向图<u,v>
d[u][0] 表示 u向子节点(向下)能到达的最远距离
d[u][1] 表示 u向子节点能到达的次远距离
*/
using namespace std;
const int MAX_N = 1e5+5;
//d[i][0]记录i为根节点时,向下的最长距离;
//d[i][1]记录i为根节点时,向下的次长距离;
// ans记录直径长度
int n, ans, d[MAX_N][2];
int l, r; // 直径两个端点
//链式前向星
int head[MAX_N], to[MAX_N << 1], nex[MAX_N << 1], v[MAX_N << 1], edge_cnt;
// 加边
void add_edge(int a, int b, int c) {
to[++edge_cnt] = b;
v[edge_cnt] = c;
nex[edge_cnt] = head[a];
head[a] = edge_cnt;
return ;
}
void dp(const int& x, const int& f) {
for (int i = head[x]; i; i = nex[i]) {
if (to[i] == f) continue;
dp(to[i], x); //递归到叶子节点 ,然后回溯回来
if (d[to[i]][0] + v[i] > d[x][0]) { //如果以x为根节点的最长链可以被它的儿子to[i]更新
d[x][1] = d[x][0]; //那么此时以x为根节点的次长链变为dp[x][0];
d[x][0] = d[to[i]][0] + v[i]; //最长链被更新
} else if (d[to[i]][0] + v[i] > d[x][1]) { //如果不能更新最长链但是却可以更新次长链
d[x][1] = d[to[i]][0] + v[i];
}
}
ans = max(ans, d[x][1] + d[x][0]); //跟新经过x的直径长度
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n - 1; i++) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
add_edge(a, b, c);
add_edge(b, a, c);
}
dp(1, 0);
// for (int i = 1; i <= n; i++) printf("d[%d] = %d\n", i, d[i]);
//printf("直径两端点:(%d,%d)\n", l, r);
printf("%d\n", ans); //直径长度
return 0;
}
习题
海贼oj421直径:http://oj.haizeix.com/problem/421
题解 :https://axieyun.top/posts/cf35.html