树的重心和中心

树的中心

定义

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

性质

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

例题

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

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

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

树的重心

定义

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

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

性质

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

例题

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

最后

以上就是野性飞鸟为你收集整理的树的重心和中心树的重心和中心的全部内容，希望文章能够帮你解决树的重心和中心树的重心和中心所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。