理解题意

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

-1

。

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

然后分别看三种操作：

$\text{Add}$ $u$ 操作：如果 $u$ 原来是叶节点，那么增加的节点就会取代它成为叶节点，叶节点数不变；如果 $u$ 不是叶节点，那么增加的节点就是新的叶节点，叶节点数 $+1$ 。
$\text{Del}$ $u$ 操作：删除了一个叶节点，叶节点数 $-1$ ，如果删除的节点的父亲在删除后也是叶节点，那么叶节点数 $+1$ 。
$\text{Upd}$ $u$ 操作：如果在换根后原来的根成为了叶节点，那么叶节点数 $+1$ ，而如果原来的叶节点变成了新的根，那么叶节点数 $-1$ 。

还要注意一个点，就是对于叶节点的判定有

2

种情况，一种是只与父亲相连，还有一种是只有一个节点的时候它自己也是叶节点。

算法实现

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

代码

CPP

#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;
}

题解：P8882 成熟时追随原神

文章操作

理解题意

算法实现

代码

相关推荐

评论

题解：P8882 成熟时追随原神