树的重心

定义

对于树上每一个顶点,分别计算其所有子树中最大子树的顶点数,当此值最小时,这个顶点即为树的重心

性质

树的重心主要有一下性质:

  • 以树的重心为根,每一子树的大小都不超过整棵树大小的一半。
  • 树中所有顶点到重心的距离和比到其它顶点距离和小,若存在多个重心则到它们的距离一致。
  • 若两棵树相连合成一颗新树,则新树的重心在原树两个重心的路径上。
  • 在树上添加或删除一个叶子,树的重心最多移动到其邻居的位置上。

求解方法

通过深度优先搜索计算每一子树的大小并记录,由$|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);
}
Last modification:May 17th, 2020 at 11:08 am
博客维护不易,如果你觉得我的文章有用,请随意赞赏