树形DP求树的重心 --SGU 134

令一个点的属性值为：去除这个点以及与这个点相连的所有边后得到的连通分量的节点数的最大值。

则树的重心定义为：一个点，这个点的属性值在所有点中是最小的。

SGU 134 即要找出所有的重心，并且找出重心的属性值。

考虑用树形DP。

dp[u]表示割去u点，得到的连通分支的节点数的最大值。

tot[u]记录以u为根的这棵子树的节点数总和（包括根）。

则用一次dfs即可预处理出这两个数组。再枚举每个点，每个点的属性值其实为max(dp[u],n-tot[u])，因为有可能最大的连通分支在u的父亲及以上。然后记录答案就可以了。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <vector>

using namespace std;

vector<int> G[];

int dp[],tot[];

vector<int> ans;

void dfs(int u)

{

    tot[u] = ;

    for(int i=;i<G[u].size();i++)

    {

        int v = G[u][i];

        if(tot[v] == -)

            dfs(v);

        else

            continue;

        dp[u] = max(dp[u],tot[v]);

        tot[u] += tot[v];

    }

}

int main()

{

    int n,i,j,u,v;

    scanf("%d",&n);

    for(i=;i<=n;i++)

        G[i].clear();

    for(i=;i<n-;i++)

    {

        scanf("%d%d",&u,&v);

        G[u].push_back(v);

        G[v].push_back(u);

    }

    memset(dp,,sizeof(dp));

    memset(tot,-,sizeof(tot));

    dfs();

    int mini = Mod;

    for(i=;i<=n;i++)

    {

        int tmp = max(dp[i],n-tot[i]);

        if(tmp < mini)

        {

            ans.clear();

            ans.push_back(i);

            mini = tmp;

        }

        else if(tmp == mini)

            ans.push_back(i);

    }

    printf("%d %d\n",mini,ans.size());

    sort(ans.begin(),ans.end());

    printf("%d",ans[]);

    for(i=;i<ans.size();i++)

        printf(" %d",ans[i]);

    puts("");

    return ;

}

巴特西

树形DP求树的重心 --SGU 134

最新文章

热门文章