树的重心与直径

代码模板基础数据结构

发布日期: 2021-09-19

更新日期: 2021-09-28

文章字数: 2.5k

阅读时长: 11 分

阅读次数:

树的重心

定义

找到一个点，当这个点成为树的根时，最大子树的结点数最小。

性质

1、一棵树最多有两个重心，且相邻。
2、一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。
3、把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。
4、树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。
5、如果以某个节点为整棵树（n个节点）的重心，那么它的每棵子树的大小都 <= (n / 2)。

利用性质1求树的重心

代码演示一

我感觉这个代码有毒，想哭，每次都用代码二，不过代码思想都一样

#include <stdio.h>

using namespace std;

#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})

#define min(a, b) ({\
    (a) < (b) ? (a) : (b);\
})

//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;
}

代码演示二


#include <stdio.h>

using namespace std;

#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})

#define min(a, b) ({\
    (a) < (b) ? (a) : (b);\
})

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://axieyun.top/posts/8419.html0

树的直径

定义

带权树上距离最远的两点

性质

1、直径两端点一点是叶子节点
2、距离任意点最远的点一定是直径的端点，这个基于贪心求直径方法的正确性可以得出
3、对于任意两棵树，如果第一棵树的直径两端点为（u，v），第二棵树直径的两端点为（x，y），
用一条边链接这两棵树，那么新树的直径一定是u，v，x，y，其中两个点。
4、若一棵树存在多条直径，那么这些直径交与一点且交点是这些直径的中点。
5、对于一棵树，如果在一个点的上接一个叶子节点，那么最多会改变直径的一个端点。

树的直径有两种求法

dfs：利用性质二，利用两边dfs即可求得直径，O(N + M)时间复杂度。
优点：能求出直径路径。
缺点：在有负权边的树无法使用。
树形dp：我们假设dis[v]为以v为根的子树到u的最长距离，那么取v的父节点u，将v和u的子树到各自的最长距离拼接在一起，即ans = max(ans, dis[v] + dis[u] + e[i].vi)，递归到叶子节点，在回溯的过程中维护dis[u] = max(dis[u], dis[v] + e[i].vi)即可。
优点：代码简单，可以求出以当前节点为根时的最长链，O(N)时间复杂度。
缺点：不能求出直径路径。

DFS利用性质二求解树的直径

、

/*
方法：
随便把一个节点x当作根节点，从该节点出发，找到距离x最远的点l即为直径的一个端点；
再从l出发，找到距离l最远的点r，r即为直径的另一个端点。在第二遍dfs过程中，
我们可以记录这条直径的路径。
*/





#include <stdio.h>

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

#include <stdio.h>

using namespace std;
#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})


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;
}

/*
思路：对于有向图<u,v>   
d[u][0] 表示 u向子节点（向下）能到达的最远距离
d[u][1] 表示 u向子节点能到达的次远距离
*/


#include <stdio.h>

using namespace std;
#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})


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;
}