考察知识点:并查集。
给定一棵具有 n n n 个节点的树,每个节点有一个初始权值 a i a_i ai。
一共需要进行 m m m 次操作,每次操作包括:
1 e
编号为
e
e
e 的边突然消失,使得它所在的那棵树变成了两棵树。
2 u val
编号为
u
u
u 的节点的权值变成了
v
a
l
val
val。
3 u
进行了一次查询,查询
u
u
u 所在的那棵树的权值之和。
现在你需要来模拟上述事件,以了解树的变迁。
由于查询是一棵树的权值之和,可以考虑使用并查集维护一个连通块的权值之和。
首先读入所有边,然后读入所有操作,将操作存起来。
如果操作是删除某个边,将该边标记,进行并查集合并时,不使用这条边。
然后倒序遍历操作:
// #pragma GCC opimize(3)
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
// #include
// #include
#define endl '\n'
#define x first
#define y second
#define fi first
#define se second
#define PI acos(-1)
// #define PI 3.1415926
#define LL long long
#define INF 0x3f3f3f3f
#define lowbit(x) (-x&x)
#define PII pair<int, int>
#define ULL unsigned long long
#define PIL pair<int, long long>
#define all(x) x.begin(), x.end()
#define mem(a, b) memset(a, b, sizeof a)
#define rev(x) reverse(x.begin(), x.end())
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e5 + 10;
struct Edge {
int u, v;
bool st;
}edges[N];
struct opion {
int op, u;
}ops[N];
int p[N], sum[N];
int n, m;
vector<int> last[N], ans;
int find(int x) {
if (x == p[x]) return x;
return p[x] = find(p[x]);
}
void merge(int a, int b) {
int pa = find(a), pb = find(b);
if (pa != pb) {
p[pa] = pb;
sum[pb] += sum[pa];
sum[pa] = 0;
}
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) {
int val; cin >> val;
last[i].push_back(val);
sum[i] = val, p[i] = i;
}
for (int i = 1; i < n; i ++ ) {
int u, v;
cin >> u >> v;
edges[i] = {u, v, true};
}
for (int i = 1; i <= m; i ++ ) {
int op, u, val;
cin >> op >> u;
if (op == 1){
edges[u].st = false;
} else if (op == 2) {
cin >> val;
last[u].push_back(val);
sum[u] = val;
}
ops[i] = {op, u};
}
for (int i = 1; i < n; i ++ ) {
Edge e = edges[i];
if (e.st) merge(e.u, e.v);
}
for (int i = m; i > 0; i -- ) {
int op = ops[i].op, u = ops[i].u;
if (op == 1) {
int a = edges[u].u, b = edges[u].v;
merge(a, b);
} else if (op == 2) {
int won = last[u].back();
last[u].pop_back();
int now = last[u].back();
sum[find(u)] += now - won;
} else if (op == 3) {
ans.push_back(sum[find(u)]);
}
}
rev(ans);
for (int it : ans) cout << it << endl;
}
int main() {
IOS;
solve();
return 0;
}