知识点：贪心，树的遍历

难度：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;
}