题解：CF1566E Buds Re-hanging

· · 题解

读完题，我们不难发现，最后的树的样子是由若干个菊花连在一起。而每一个菊花就是一个芽。所以，我们考虑找出所有的芽，将他们连在一起。我们可以先搜索一遍，找到所有可以做芽。在搜索的过程中，每找到一个芽，就把这个芽从原树上分离开，统计芽的个数。设我们现在找到了 x 个芽，那么我们的答案应为 n - 2x + 1，其中 n - 2x 代表除去一个叶子节点外多出来的叶节点数，然后再加上整体合并而必然产生的一个叶节点。但是，因为根节点是不可以连接的，所以，如果根节点也是一个芽，那么芽的个数就要减一。

接下来是代码环节：

#include<bits/stdc++.h>
using namespace std;
int t, n;
bool mark[200005];
vector<int> v[200005];
void dfs(int u, int father) {
    bool p = false;
    for (auto i : v[u]) {
        if (i != father) {
            dfs(i, u);
            p |= mark[i];
        }
    }
    mark[u] = !p;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t --) {
        cin >> n;
        for (int i = 1; i < n; i ++) {
            int x, y;
            cin >> x >> y;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        dfs(1, 1);
        int ans = 0;
        for (int i = 1; i <= n; i ++) {
            if (!mark[i]) {
                ans ++;
            }
        }
        ans = n - (ans - 1) * 2 - 1;
        if (mark[1]) {
            ans --;
        }
        cout << ans << "\n";
        for (int i = 1; i <= n; i ++) {
            v[i].clear();
            mark[i] = false;
        }
    }
    return 0;
}