寻找树的重心 - dblank

寻找树的重心

树的重心是该节点的最大子树节点最小。树的重心在树上的分治经常用到。

我们可以用树形dp来求树的重心,复杂度是O(n), 用son[i]表示节点i的子树节点个数,u为i节点的一个儿子节点,那么该节点的最大子树节点数为max(n-1-son[i], son[u] + 1)。

poj 1655

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 200000 + 10, Mod = 1000000000;
typedef long long ll;
struct node
{
    int next, to;
} path[N];
int vis[N], head[N],n, ans, cnt, size, son[N];
void init()
{
    cnt = 0;
    size = inf;
    ans = 0;
    memset(head, -1, sizeof(head));
    memset(vis, 0, sizeof(vis));
    memset(son, 0, sizeof(son));
}
void add(int u, int v)
{
    path[cnt].to = v;
    path[cnt].next = head[u];
    head[u] = cnt++;
}
void dfs(int cur)
{
    vis[cur] = 1;
    int tmp = 0;
    for(int i = head[cur]; ~i; i = path[i].next)
    {
        int u = path[i].to;
        if(!vis[u])
        {
            dfs(u);
            son[cur] += son[u] + 1;
            tmp = max(son[u] + 1, tmp);
        }
    }
    tmp = max(tmp, n-1-son[cur]);
    if(tmp < size || tmp == size && cur < ans)
        ans = cur, size = tmp;
}
int main()
{
    int t, u, v;
    scanf("%d", &t);
    while(t--)
    {
        init();
        scanf("%d", &n);
        for(int i = 1; i<n; i++)
        {
            scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
        }
        dfs(1);
        printf("%d %dn", ans, size);
    }
    return 0;
}

poj 3107

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 200000 + 10, Mod = 1000000000;
typedef long long ll;
struct node
{
    int next, to;
} path[N];
int vis[N], head[N],n, ans, cnt, size, son[N], mx[N];
void init()
{
    cnt = 0;
    size = inf;
    ans = 0;
    memset(head, -1, sizeof(head));
    memset(vis, 0, sizeof(vis));
    memset(son, 0, sizeof(son));
    memset(mx, 0, sizeof(mx));
}
void add(int u, int v)
{
    path[cnt].to = v;
    path[cnt].next = head[u];
    head[u] = cnt++;
}
void dfs(int cur)
{
    vis[cur] = 1;
    int tmp = 0;
    for(int i = head[cur]; ~i; i = path[i].next)
    {
        int u = path[i].to;
        if(!vis[u])
        {
            dfs(u);
            son[cur] += son[u] + 1;
            tmp = max(son[u] + 1, tmp);
        }
    }
    tmp = max(tmp, n-1-son[cur]);
    mx[cur] = tmp;
    size = min(size, tmp);
}
int main()
{
    int t, u, v;
    while(~scanf("%d", &n))
    {
        init();
        for(int i = 1; i<n; i++)
        {
            scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
        }
        dfs(1);
        int ok = 0;
        for(int i = 1; i<=n; i++)
        {
            if(mx[i] == size)
            {
                if(!ok) printf("%d", i), ok = 1;
                else printf(" %d", i);
            }
        }
        printf("n");
    }
    return 0;
}

 

发表新评论