poj1655 dfs序+暴力

题意就是给你一棵树，然后去掉一个节点，求去掉哪个节点他的剩下的树的最大节点数最少。输出节点和最大子树节点数。
由树dp专题看见这题，但是嘛。。。。。我第一眼都没意识到他是个dp。
我的做法是这样的，就跑就只跑一遍dfs序，然后途中记录一下每个节点的父亲是谁。在暴力跑每一个点的答案。
遍历每一个点的答案怎么出来呢？就是dfs序后，我们可以得知每一个点与其所有子树的范围在哪里。去掉这一个点，也就是说，吧这个点相连的所有线断开。对于这个点的子树，我们可以知道每个子树他一共含有多少个节点（dfs序出来的）。然后去判断每个子树的节点最大值，这是子树是考虑。父亲呢？其实你想一下，你砍掉一个点，他与父亲相连的砍完，是不是那一颗与父亲节点相连的子树数目就是总的节点数，减去你要砍这个点以及他所有节点的数目。那为什么不是单纯判断父亲节点的dfs序所记录的子节点的总数？因为要砍掉这个点的父亲节点，他上面可能还有好多层，所以就不能只算要砍节点的父亲节点的子树节点总数。

如果有任何不懂可以留言。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const long long max_ = 2e4 + 50;
int head[max_], n, xiann = 1, chu[max_], ru[max_], father[max_], cnt = 0;
inline int read()
{
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}

struct k {
	int next, to;
}xian[max_ * 2];
void dfs(int now, int fa) {
	ru[now] = ++cnt;
	father[now] = fa;
	for (int i = head[now]; i; i = xian[i].next) {
		if (xian[i].to != fa) {
			dfs(xian[i].to, now);
		}
	}
	chu[now] = cnt;
}
void add_(int a, int b) {
	xian[xiann].next = head[a];
	xian[xiann].to = b;
	head[a] = xiann;
	xiann++;
}
int main() {
	int T = read();
	while (T--) {
		n = read();
		for (int i = 1; i <= n - 1; i++) {
			int a = read(), b = read();
			add_(a, b); add_(b, a);
		}
		dfs(1, -1);
		int ans = 1e9, dian;
		for (int i = 1; i <= n; i++) {
			int temp = 1;
			for (int j = head[i]; j; j = xian[j].next) {
				int to = xian[j].to;
				if (to == father[i]) continue;//这一句一定要加，因为父亲的情况我们在下面判断了，这里不能判断，不然会wa
				temp = max(temp, (chu[to] - ru[to] + 1));
			}
			if (father[i] != -1) {
				temp = max(temp, (n - (chu[i] - ru[i] + 1)));
			}
			if (ans > temp) {
				ans = temp;
				dian = i;
			}
		}
		cout << dian << " " << ans << endl;
		xiann = 1, cnt = 0;
		for (int i = 0; i <= n; i++) {
			head[i] = father[i] = chu[i] = ru[i] = xian[i].next = xian[i].to = 0;
		}
		//getchar();
	}
	return 0;
}