【BZOJ】3391: [Usaco2004 Dec]Tree Cutting网络破坏（dfs）

http://www.lydsy.com/JudgeOnline/problem.php?id=3391

显然判断每个点只需要判断子树是否小于等于n/2即可

那么我们虚拟一个根，然后计算每个子树的size，而这个点的子树的size和n-这个点的size就是我们需要找的

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr2(a, b, c) for1(i, 1, b) { for1(j, 1, c) cout << a[i][j]; cout << endl; }

#define printarr1(a, b) for1(i, 1, b) cout << a[i]; cout << endl

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

const int N=10005;

int sz[N], ihead[N], vis[N], mark[N], n, cnt;

struct ED { int to, next; }e[N+N];

void add(int u, int v) {

	e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v;

	e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u;

}

void dfs(int x) {

	sz[x]=vis[x]=1;

	int v, mx=0;

	for(int i=ihead[x]; i; i=e[i].next) if(!vis[v=e[i].to]) {

		dfs(v);

		sz[x]+=sz[v];

		mx=max(sz[v], mx);

	}

	mx=max(mx, n-sz[x]);

	if(mx<=(n>>1)) mark[x]=1;

}

int main() {

	read(n);

	for1(i, 1, n-1) add(getint(), getint());

	dfs((n+1)>>1);

	for1(i, 1, n) if(mark[i]) printf("%d\n", i);

	return 0;

}

Description

约翰意识到贝茜建设网络花费了他巨额的经费，就把她解雇了．贝茜很愤怒，打算狠狠报

复．她打算破坏刚建成的约翰的网络．约翰的网络是树形的，连接着 N(1≤N≤10000)个牛棚．她打算切断某一个牛棚的电源，使和这个牛棚相连的所有电缆全部中断．之后，就会存在若干子网络．为保证破坏够大，每一个子网的牛棚数不得超过总牛棚数的一半,那哪些牛棚值得破坏呢？

Input

第1行：一个整数N.

第2到N+1行：每行输入两个整数，表示一条电缆的两个端点．

Output

按从小到大的顺序，输出所有值得破坏的牛棚．如果没有一个值得破坏，就输出“NONE”．

Sample Input

10
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
3 8

Sample Output

3
8

如果牛棚3或牛棚8被破坏，剩下的三个子网节点数将是5，2，2，没有超过5的．
来源信息

HINT

Source

Silver

巴特西