【傳智杯】第三屆“傳智杯”全國大學生IT技能大賽（初賽A組）G - 森林 | 并查集、思維

題目大意：

清蒸魚是一個盡職盡責的 YYH Land 護林者，他負責每天維護 YYH Land 的森林，在最開始的時候，YYH Land 只有一棵具有 n n n 個節點的樹，每個節點有一個靈力值 v v v，

由于 YYH Land 是一片神奇的國度，YYH Land 的樹也有一些神奇的能力，具體來說它滿足如下操作：

• 1 e

編號為 e e e 的邊突然消失，使得它所在的那棵樹變成了兩棵樹，

• 2 u u u v a l val val

編號為 uu 的節點的靈力值變成了 valval，

• 3 u u u

清蒸魚進行了一次查詢，查詢 uu 所在的那棵樹的靈力值之和，

現在你需要幫助清蒸魚，來模擬上述事件，以了解森林的變遷，

題目思路：

看到加邊、減邊的操作，向并查集上靠攏就可以了
由于這題只限于刪邊，并且伴隨著權值改變
顯然，刪邊操作是不好維護靈力值的
但是，加邊操作對于每一塊的靈力值的改變，是非常好維護的
假設只有加邊操作，那么對于一個點x的靈力值發生變化，那么就有點x的的根（并查集尋根）增加 n e w v a l ? l a s t v a l newval - lastval newval?lastval就可以了
所以考慮把操作離線儲存后，倒敘處理（減邊換為加邊）
對于權值的變化 也對應取反就好了
注意倒敘處理前，應該要保存操作完之后圖的權值及分塊情況，之后在此圖上進行操作，而不是直接 n n n個點上進行操作

Code：

/*** keep hungry and calm CoolGuang!  ***/
/*#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)*/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define d(x) printf("%lld\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17;
const ll maxn = 4e5+700;
const int mod= 1e9+7;
const int up = 1e9;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int pre[maxn];
ll num[maxn],val[maxn];
pair<int,int>e[maxn];
vector<int>v[maxn];
int vis[maxn];
int Find(int x){
    return pre[x]==x?x:pre[x] = Find(pre[x]);
}
struct node{
    int op,x,y;
}q[maxn];
ll res[maxn];
int main(){
    read(n);read(m);
    for(int i=1;i<=n;i++){
        read(num[i]);
        val[i] = num[i];
        pre[i] = i;
        v[i].push_back(num[i]);
    }
    for(int i=1;i<=n-1;i++){
        int x,y;read(x);read(y);
        e[i] = {x,y};
    }
    for(int i=1;i<=m;i++){
        read(q[i].op);
        if(q[i].op == 1){
            read(q[i].x);
            vis[q[i].x] = 1;
        }
        else if(q[i].op == 2){
            read(q[i].x);
            read(q[i].y);
            v[q[i].x].push_back(q[i].y);
        }else read(q[i].x);
    }
    for(int i=1;i<=n;i++)
        if(v[i].size())
            val[i] = num[i] = v[i].back();
    for(int i=1;i<=n-1;i++){
        if(vis[i]) continue;
        int dx = Find(e[i].first),dy = Find(e[i].second);
        if(dx != dy){
            pre[dx] = dy;
            val[dy] += val[dx];
        }
    }
    for(int i=m;i>=1;i--){
        if(q[i].op == 1){
            int dx = Find(e[q[i].x].first),dy = Find(e[q[i].x].second);
            if(dx != dy){
                pre[dx] = dy;
                val[dy] += val[dx];
            }
        }else if(q[i].op == 2){
            v[q[i].x].pop_back();
            int dx = Find(q[i].x);
            val[dx] += v[q[i].x].back() - num[q[i].x];
            num[q[i].x] = v[q[i].x].back();
        }
        else res[i] = val[Find(q[i].x)];
    }
    for(int i=1;i<=m;i++){
        if(res[i])
            printf("%lld\n",res[i]);
    }
    return 0;
}

/***
5 7
1 2 3 4 5
1 2
2 3
3 4
4 5

3 1
3 2
2 1 5
1 2
2 1 3
3 1
3 5
****/