P1395 会议

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int head[MAXn + 10], cntnex, nex[MAXm * 2 + 10], to[MAXm * 2 + 10];
void Insert(int u, int v) {
    nex[++cntnex] = head[u];
    head[u] = cntnex;
    to[cntnex] = v;
}

int n;
bool vis[MAXn + 10]; int siz[MAXn + 10], w[MAXn + 10], cen[2];
void EvaCen(int cur) {
    vis[cur] = 1;
    siz[cur] = 1;
    w[cur] = 0;
    for (re int i = head[cur]; i; i = nex[i]) {
        if (vis[to[i]]) continue;
        EvaCen(to[i]);
        siz[cur] += siz[to[i]];
        w[cur] = max(w[cur], siz[to[i]]);
    }
    w[cur] = max(w[cur], n - siz[cur]);
    if (w[cur] <= n / 2) {
        cen[cen[0] != 0] = cur;
    }
}

EvaCen(1);