Algoogle

Algorithm for Programming Contest

PKU 2378 Tree Cutting

Category: PKU Tag: dfs

Tree Cutting

問題概要


全域木が与えられるので, 取り除いた時にできる部分木の節点の個数がN/2以下になるような節点をすべて求める.

解法


適当な点から始めてDFSしていく.
各節点から出てる辺の先の節点以下の部分木の大きさを見ていく.
DFSで来る前の節点以下の部分木は全体から他の和を引けばよい.
各DFSは来る前の節点と現在の節点を結ぶ辺を切った時の部分期の大きさを返すようにする.

コード


(2378.cpp) download
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

int N;
vector<int> edge[10010];
vector<int> ans;

int dfs(int p, int from){
    int ret = 1, tmp;
    bool ok = 1;
    for(int i = 0; i < edge[p].size(); i++){
        if(edge[p][i] == from) continue;
        tmp = dfs(edge[p][i], p);
        if(tmp > N / 2) ok = 0;
        ret += tmp;
    }
    tmp = N-ret;
    if(tmp > N / 2) ok = 0;
    if(ok) ans.push_back(p+1);
    return ret;
}

int main(){
    scanf("%d", &N);
    for(int i = 0; i < N-1; i++){
        int a, b; scanf("%d%d", &a, &b);
        a--; b--;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    dfs(0, 0);
    sort(ans.begin(), ans.end());
    if(ans.size() == 0) printf("NONE\n");
    else {
        for(int i = 0; i < ans.size(); i++)
            printf("%d\n", ans[i]);
    }
    return 0;
}

Comments