题解：P8827 [传智杯 #3 初赛] 森林

· · 题解

先看题：

  1. 操作一，删除编号为 e_i 的边。
  2. 操作二，把编号为 u_i 的点的权值改成 v_i 。
  3. 操作三，询问编号为 u_i 的点所在的子树的权值和。

很明显，如果没有操作一，这提示能用并查集吊打的。但是他是绿题，所以有操作一。

因为初始时是一棵树，所以在删除一些边后他就是森林了。好，那这题就能用 LCT 并查集切掉。

因为正着来的话删边会很麻烦，所以先离线，然后倒着来。这样删边就转化成了连接 u 和 v ，把 u 的点权改成 v 就变成了把 u 的点权改成上一次操作的 v ，询问子树和可以用并查集维护。因为是倒着来的，所以输出答案时可以用一个栈存储。

warning：合并时要注意，一般的并查集都是这样写的 fa[find (u)] = find (v);，所以合并子树和的时候是 sum[find (v)] += sum[find (u)];。

注意一下下标之类的细节就好了，代码还是很容易实现的。

code：

# include "bits/stdc++.h"
# define int long long
using namespace std;
namespace chtholly
{
    template <const int N>
    class UFDS
    {
        private :
            int s[N];
            int a[N];
            int fa[N];
        public :
            int find (int u)
            {
                return u == fa[u] ? u : fa[u] = find (fa[u]);
            }
            void merge (int u, int v)
            {
                u = find (u);
                v = find (v);
                if (u != v)
                {
                    fa[u] = v;//这里是把子树 u 合并到 v 上，所以合并子树和的时候是如下写法。
                    s[v] += s[u];
                }
            }//合并。
            void init ()
            {
                for (int i = 1; i < N; i ++) fa[i] = i;
            }//初始化。
            int sum (int u)
            {
                return s[find (u)];
            }//子树和。
            void change (int u, int x)
            {
                int f = find (u);
                s[f] += x - a[u];
                a[u] = x;
            }//单点修改，因为是把点 u 的值改成 x，所以把子树和加上 x 再减去 u 本身的值就好了。
    };//以上为并查集
}
using namespace chtholly;
# define stdi stdin
# define stdo stdout
UFDS <100012> tree;
int n, m, a[100012];
bool f[100012];
int u[100012], v[100012], last[100012];
int op[100012], x[100012], y[100012];
signed main ()
{
    cin >> n >> m;
    tree.init ();
    for (int i = 1; i <= n; i ++)
    {
        int num; cin >> num;
        a[i] = num;
    }
    for (int i = 1; i < n; i ++)
    {
        cin >> u[i] >> v[i];
        f[i] = 1;
    }
    for (int i = 1; i <= m; i ++)
    {
        cin >> op[i] >> x[i];
        if (op[i] == 1) f[x[i]] = 0;
        if (op[i] == 2)
        {
            cin >> y[i];
            tree.change (x[i], y[i]);
            last[i] = a[x[i]]; //记录上一次的操作后的值。
            a[x[i]] = y[i];
        }
    }
    for (int i = 1; i <= n; i ++) tree.change (i, a[i]);
    for (int i = 1; i < n; i ++)
    {
        if (f[i])
        {
            tree.merge (u[i], v[i]);
        }
    }
//  cout << "sum : ";
//  for (int i = 1; i <= n; i ++) cout << tree.sum (i) << ' ';
//  cout << endl;
    vector <int> q;
    for (int i = m; i >= 1; i --)
    {
        if (op[i] == 1) tree.merge (u[x[i]], v[x[i]]);
        if (op[i] == 2) tree.change (x[i], last[i]);
        if (op[i] == 3) q.push_back (tree.sum (x[i]));
    }
    while (not q.empty ()) cout << q.back () << endl, q.pop_back ();
}