树的重心和中心树的重心和中心

80 阅读 0 评论 53 点赞

我是靠谱客的博主野性飞鸟，这篇文章主要介绍树的重心和中心树的重心和中心，现在分享给大家，希望可以做个参考。

树的重心和中心

树的中心

定义

树上任意一条直径所在的链的中点，当直径为偶数的时候，中心由一个点 $(u)$ 构成。当直径为奇数的时候，中心由两个点构成 $(u, v)$ 。

性质

树的中心是唯一的，有一个且仅有一个中心
树上任意一个节点 $u$ 到另外一个任意节点 $v$ 的的距离是最大值，那么 $v$ 为树上直径两个端点的其中一个。

例题

如何寻找树的中心，定义函数 $F a r (x) = y$ 为节点 $x$ 到所有节点的最远节点 $y$ 。

首先，我们任意指定一个节点 $k$ ，求得 $A = F a r (k)$ ，则 $A$ 为直径的一个端点，然后我们求得 $B = F a r (A)$ ，那么节点 $A B$ 和其唯一的一条路径将是这颗树的一个直径。

ABC 221F

对树进行中心分解，分解得到几个连通分量，计算连通分量的路径最长的节点数，计算答案。

复制代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
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;
}

树的重心

定义

树上的每一个节点都有一个平衡值，该平衡值的定义为，以该节点为根节点，所有子树中节点数量最大的那个子树中节点数量。

树的重心是树上的一个节点，其平衡值是树中节点中最小的那个。

性质

以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

例题

POJ 1655

对整棵树进行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 %dn", ans, cnt);
    }

return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#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 %dn", ans, cnt);
    }

    return 0;
}

最后

以上就是野性飞鸟最近收集整理的关于树的重心和中心树的重心和中心的全部内容，更多相关树内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：# 图论
浏览次数：80 次浏览
发布日期：2024-09-18 20:35:02
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_7_o_10_fw_13__7_k4.html

树的重心和中心树的重心和中心

树的重心和中心

树的中心

定义

性质

例题

树的重心

定义

性质

例题

最后

评论列表共有 0 条评论

发表评论取消回复

树的重心和中心树的重心和中心

树的重心和中心

树的中心

定义

性质

例题

树的重心

定义

性质

例题

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复