链接

• 点此跳转

思路

考察知识点：并查集。

题目描述

给定一棵具有 nnn 个节点的树，每个节点有一个初始权值 aia_iai​。

一共需要进行 mmm 次操作，每次操作包括：

• 1 e 编号为 eee 的边突然消失，使得它所在的那棵树变成了两棵树。

• 2 u val 编号为 uuu 的节点的权值变成了 valvalval。

• 3 u 进行了一次查询，查询 uuu 所在的那棵树的权值之和。

现在你需要来模拟上述事件，以了解树的变迁。

分析

由于查询是一棵树的权值之和，可以考虑使用并查集维护一个连通块的权值之和。

首先读入所有边，然后读入所有操作，将操作存起来。

如果操作是删除某个边，将该边标记，进行并查集合并时，不使用这条边。

然后倒序遍历操作：

• 如果是删除边，将两点所在并查集合并。
• 如果是查询，直接查询祖宗节点，将祖宗节点的存的权值之和加入答案。
• 如果是将点赋值。首先查询该点的根节点，然后取出该点上一次的值，然后在权值之和减去该点两次值的差。

AC代码

// #pragma GCC opimize(3)
#include 
#include