[Poj 3107] Godfather 链式前向星+树的重心

题意

http://poj.org/problem?id=3107

给定一棵树，找到所有重心，升序输出，n<=50000。

链式前向星存储图

链式前向星是前向星的升级版本，是一种特殊的边集数组，有n条边，数组开n*2，切记！切记！！（由于要正反两次存边，也就是一条边要存两次），空间利用率高，并且速度比使用vector快，本题使用vector就TLE了一次。。

建立如下结构体：

struct node{

	int to,next,w;

}edge[maxe]

其中edge[i].to表示第i条边的终点，edge[i].next表示与第i条边同起点的下一条边的存储位置(使用链式前向星存储遍历的时候是逆序遍历的，所有这里其实是前一条边的位置），edge[i].w表示第i条边的权值

inline void add(int u,int v,int w){

	edge[cnt].w=w,edge[i].to=v;

	edge[cnt].next=head[u];

	head[u]=cnt++;

}

初始cnt=0,表示第几条边

其中head[u]表示以u为起点的第一条边的存储位置，实际上，由于head[u]的值会不断被覆盖，存储的实际上是最后一条边的位置，遍历的时候其实是逆序遍历的

head[]一般初始化为-1

遍历以u节点为起始位置的所有边，终止位置i=-1

for(int i=head[u];~i;i=edge[i].next)

更详细的解释参考这篇博客：https://blog.****.net/acdreamers/article/details/16902023

树的重心

树的重心也叫树的质心，删除这个节点后，所有子树中最大子树节点数最小，也就是删点之后生成的多颗树尽可能平衡。

性质

1. 树中所有节点到某个点的距离之和，到重心的距离和是最小的。
2. 两棵树通过一条边相连，新树的重心在原来两棵树的重心连线上。
3. 一棵树添加或删除一个节点，树的重心最多只移动一条边的位置。
4. 一棵树最多两个重心，且相邻

算法实现

只需一遍dfs，复杂度O(n)，遍历过程中找到以每个节点为根的子树中最大的子树（节点数最多），在所有最大子树中取最小值。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxe=5e4+5;

int n;

int mNode,mBalacne=0x7f7f7f7f;

int scld[maxn];

struct node{

    int to,next;

}edge[maxe*2];

int head[maxn],cnt=0;

inline void add(int x,int y){

    edge[cnt].to=y;

    edge[cnt].next=head[x];

    head[x]=cnt++;

}

int ans[maxn],id=0;

void dfs(int u,int pa){

    int maxSubT=0;

    scld[u]=1;

    for(int i=head[u];~i;i=edge[i].next){

        int cld=edge[i].to;

        if(cld!=pa){

            dfs(cld,u);

            scld[u]+=(scld[cld]);

            //找除从父亲节点出发的那颗子树外，剩下的最大子树的节点个数的最大值

            maxSubT=max(maxSubT,scld[cld]);

        }

    }

    //最后和从父亲节点出发的那颗子树比较，找到以当前节点为根的最大子树

    //这里的子树都是不包括当前节点的

    maxSubT=max(maxSubT,n-scld[u]);

   // cout<<u<<":"<<scld[u]<<" "<<maxSubT<<" "<<mBalacne<<endl;

    if(maxSubT<mBalacne){

        id=0,ans[id++]=u;

        mBalacne=maxSubT;

    }

    else if(maxSubT==mBalacne){

        ans[id++]=u;

    }

    //cout<<id<<endl;

}

int main(){

    memset(head,-1,4*maxn);

    cin>>n;

    int x,y;

    for(int i=0;i<n-1;i++){

        scanf("%d%d",&x,&y);

        add(x,y);add(y,x);

    }

    dfs(1,0);//随便取一个节点开始遍历

    sort(ans,ans+id);

    for(int i=0;i<id;i++){

        if(i)putchar(' ');

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

    }

    return 0;

}

/*

6

1 2

1 3

2 4

2 5

5 6

6

1 3

1 4

1 5

2 3

2 6

6

1 2

1 4

1 3

2 5

4 6

*/