poj 3107 Godfather(树的重心)

dfs求树的重心。

然后记得用前向星，用vector会t。

然后就是又是惯例的poj过量测试，数组开大一点。

代码：

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define ps push_back
using namespace std;
const int maxn=5e5+5;
//vector<int>edg[maxn];
struct node
{
    int to;
    int nex;
}edg[maxn+10000];
int head[maxn];
int siz[maxn];
int ms[maxn];
vector<int>ans;
int cnt;
void add(int u, int v)
{
    edg[cnt].to=v;
    edg[cnt].nex=head[u];
    head[u]=cnt++;
}

void dfs(int x, int fa)
{
    siz[x]=ms[x]=0;
//    for(int i=0; i<(int)edg[x].size(); i++)
    for(int i=head[x]; i!=-1; i=edg[i].nex)
    {
        if(edg[i].to!=fa)
        {
            dfs(edg[i].to, x);
            siz[x]+=siz[edg[i].to];
            ms[x]=max(ms[x], siz[edg[i].to]);
        }
    }
    siz[x]++;
//    cout<<x<<" "<<siz[x]<<endl;
    return;
}

int main()
{
    int x, y, n, i, j;

    cin>>n;
    for(i=1; i<=n; i++)head[i]=-1;
    for(i=0; i<n-1; i++)
    {
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);

    }

    dfs(1, 0);
    int mi=maxn+10;
    for(i=1; i<=n; i++)
    {
        ms[i]=max(ms[i], n-siz[i]);
        if(ms[i]<mi)
        {
            mi=ms[i];
        }

    }
    for(i=1; i<=n; i++)
    {
        if(ms[i]==mi)
            {
                ans.ps(i);
            }
    }
    sort(ans.begin(), ans.end());
    printf("%d", ans[0]);
    for(i=1; i<(int)ans.size(); i++)
    {
        printf(" %d", ans[i]);
    }
    printf("\n");


    return 0;
}