(TOJ) 293.樹重心

http://sprout.tw/oj/pro/293/

本題就是要求樹的重心

樹重心定義：使得「拔除某節點後，形成的若干棵樹分別的節點數量中的最大值」<=樹的大小/2。

題目中有範例。

要怎麼解呢？

如果把它看成一棵樹，我們會需要維護的是 1.兒子的總合 2.眾多兒子中的最大的那個

因為我們要取若干棵節點數量中的最大值，那父節點就是(全部節點 - 兒子節點總合 - 自己)，那就是max (父節點, 眾多兒子中的最大)。

那就一次dfs就可以完成了！

阿對了，哪個點當根都可以，所以我的code是用random

//樹重心


#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <ctime>
using namespace std;

const int MAX_N = 100003;

vector<int> edg[MAX_N];

struct Node {
    int val;
    int sum;
    int max;
} node[MAX_N];

bool visit[MAX_N];

int dfs(int id) {
    visit[id]=true;
    int len=edg[id].size();
    for (int x=0;len>x;x++) {
        int tmp=edg[id][x];
        if (visit[tmp]==true) ;  //回到父親
        else {
            int t=dfs(tmp);
            node[id].sum+=t;
            node[id].max = max(node[id].max,t);
        }
    }
    return node[id].sum+1;
}

int main () {
    srand(time(NULL));
    int T;
    scanf("%d",&T);
    while (T--) {
        int n;
        scanf("%d",&n);
        //init
        for (int x=0;n>x;x++) {
            edg[x].clear();
            node[x].sum=node[x].max = 0;
            node[x].val = x;
            visit[x]=false;
        }
        for (int x=0;n-1>x;x++) {
            int a,b;
            scanf("%d %d",&a,&b);
            edg[a].push_back(b);
            edg[b].push_back(a);
        }
        int id = rand() % n;
        dfs(id);
        int ans=n;
        for (int x=0;n>x;x++) {
            int tmp=max(node[x].max,n-node[x].sum-1);
            ans=min(ans,tmp);
        }
        for (int x=0;n>x;x++) {
            int tmp=max(node[x].max,n-node[x].sum-1);
            if (tmp==ans) {
                printf("%d\n",x);
                break;
            }
        }
        
    }
}