题解：P8882 成熟时追随原神

hyx761 · 2025-02-09 10:32:31 · 题解

理解题意

注意到对于每一个非叶节点，它与它的儿子之间都会被连接上一条道路，而对于一棵树来说，任意两个节点之间只有一种走法，连接两个节点，联通块数一定 -1。

而原先没有道路时，每一个节点都是一个独立的联通块，减去了非叶节点数，那么题目问的本质上就是：叶节点数！

然后分别看三种操作：

还要注意一个点，就是对于叶节点的判定有 2 种情况，一种是只与父亲相连，还有一种是只有一个节点的时候它自己也是叶节点。

算法实现

使用邻接表存储，并且维护叶节点数以及根节点（判叶节点的时候用到）

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, u, leaf, root = 1, tmp;
string op;
vector <int> to[400010];
bool check(int x)
{
    return x == root and to[x].size() == 0 or x != root and to[x].size() == 1;
}
signed main()
{
    ios :: sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        cin >> u;
        to[i].push_back(u);
        to[u].push_back(i);
    }
    for (int i = 1; i <= n; i++) if (check(i)) leaf++;
    cout << leaf << endl;
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> op >> u;
        if (op == "Add")
        {
            if (not check(u)) leaf++;
            to[u].push_back(n + i);
            to[n + i].push_back(u);
        }
        if (op == "Del") 
        {
            to[to[u][0]].erase(remove(to[to[u][0]].begin(), to[to[u][0]].end(), u), to[to[u][0]].end());
            if (not check(to[u][0])) leaf--;
        }
        if (op == "Upd")
        {
            tmp = root;
            root = -1;
            if (check(tmp)) leaf++;
            if (check(u)) leaf--;
            root = u;
        }
        cout << leaf << endl;
    }
    return 0;
}