记录编号	38453	评测结果	AAAWWWWAWW
题目名称	[SOJ 1140] 国王的遗产	最终得分	40
用户昵称	王者自由	是否通过	未通过
代码语言	C++	运行时间	0.521 s
提交时间	2012-04-19 13:13:37	内存使用	0.98 MiB

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 30000 + 10, K = 100 + 10;
int n, k, x, y;
int T, R, S, e, g, r;
int c[N], t[N], p[N];
bool l[N];
vector<int> G[N];
void DFS(int u, int fa) {
    t[u] = 1;
    c[u] = u;
    int v;
    for(int i=0; v=G[u][i], i<G[u].size(); i++)
        if(v != fa && !l[v]) {
            DFS(v, p[v] = u);
            t[u] += t[v];
            c[u] = min(c[u], c[v]);
            if((t[v] <= g / 2 && t[v] > T) || (t[v] == T && c[v] < S)) {
                T = t[v];
                S = c[v];
                R = v;
            }
        }
}
void DFS2(int u, int fa) {
    int num;
    int v;
    for(int i=0; v=G[u][i], i<G[u].size(); i++)
        if(v != fa && !l[v]) {
            DFS2(v, u);
            num = g - t[v];
            if((num <= g / 2 && num > T) || (num == T && R > 0)) {
                T = num;
                S = c[v];
                R = -v;
            }
        }
}
void Update1(int u, int fa) {
    l[u] = 1;
    int v;
    for(int i=0; v=G[u][i], i<G[u].size(); i++)
        if(v != fa && !l[v])
            Update1(v, u);
}
void Update2(int u, int fa) {
    l[u] = 1;
    int v;
    for(int i=0; v=G[u][i], i<G[u].size(); i++)
        if(v != fa && !l[v] && v != -R)
            Update2(v, u);
}
int main() {
    freopen("legacy.in", "r", stdin);
    freopen("legacy.out", "w", stdout);
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++) {
        scanf("%d %d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
        sort(G[i].begin(), G[i].end());
    r = 1, g = n;
    for(int i=1; i<k; i++) {
        while(l[r]) r++;
        T = 0, p[r] = 0;
        DFS(r, 0);
        DFS2(r, 0);
        if(R > 0)
            Update1(R, p[R]);
        else
            Update2(r, 0);
        printf("%d ", T);
        g -= T;
    }
    printf("%d\n", g);
    return 0;
}