CF120F Spiders

知识点：贪心，树的遍历

难度：5

我真的是操了，这已经不知道是多少次因为无向边而把数组开小导致一直卡着，这个题的题意就是有若干棵无根树，问把这些树拼接起来最长的直径能有多少，总体的思路就是对于每个无根树，我们都让他们贡献出最长的直径，这样拼接起来得到的树一定直径最长，题解里面说了还好是最长，那么这样是比较简单的，这样贪心即可，看来如果是最短那么会更难一点，

然后就是子操作，如何求一个无根树的最长的直径，看题解里面说了有两种方法，一种是两遍的dfs或bfs，一种是树形dp，那么我现在肯定只能用搜索来做，具体的方法就是我们先任取一个点，求出以他为根的最深的节点，然后再以那个最深的节点为根再进行一次dfs，这样第二次求出来的最深的深度就是这个无根树的最长的直径，第一次接触无根树的概念，不是很熟悉，无根树虽然边的数目也是顶点数减一，但是边是无向的，所以我们涉及到边的数组要开成原来的2倍，

一开始想的暴力求无根树直径做法超时了，也是很不懂为啥会超时，

#include 
 
using namespace std;
 
const int N = 105;
 
int tot, ver[N * 2], nxt[N * 2], head[N];
int n, vis[N], dep[N], dmax, root;
 
void add(int x, int y) {
	ver[++tot] = y;
	nxt[tot] = head[x]; head[x] = tot;
}
 
void dfs(int v) {
	vis[v] = 1;
	for (int i = head[v]; i; i = nxt[i]) {
		int y = ver[i];
		if (vis[y]) continue;
		dep[y] = dep[v] + 1;
		if (dep[y] > dmax) {
			dmax = dep[y];
			root = y;
		}
		dfs(y);
	}
}
 
int main() {
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	int T;
	cin >> T;
	int ans = 0;
	while (T--) {
		tot = 0;
		memset(head, 0, sizeof(head));
		memset(vis, 0, sizeof(vis));
		memset(dep, 0, sizeof(dep));
		dmax = -1;
		cin >> n;
		for (int i = 1; i <= n - 1; i++) {
			int x, y;
			cin >> x >> y;
			add(x, y);
			add(y, x);
		}
		dfs(1);
		memset(vis, 0, sizeof(vis));
		memset(dep, 0, sizeof(dep));
		dmax = -1;
		dfs(root);
		ans += dmax;
	}
	cout << ans;
	return 0;
}