• 传智杯#5练习赛_树的变迁


    链接

    思路

    考察知识点:并查集

    题目描述

    给定一棵具有 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 所在的那棵树的权值之和。

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

    分析

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

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

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

    然后倒序遍历操作:

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

    AC代码

    // #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;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
  • 相关阅读:
    Java8新特性:stream流应用,丢掉for循环实现复杂遍历功能
    【广州华锐互动】利用AR进行野外地质调查学习,培养学生实践能力
    LeetCode每日一题——2562. Find the Array Concatenation Value
    Android:RecyclerView的ChildHelper
    Nacos 注册中心入门及使用
    【EDA365电子论坛】硬件人经历南下、北上,回乡创业,后悔了吗?
    音视频封装demo:使用libmp4v2将h264视频数据和aac语音数据封装(mux)成mp4文件
    线控制动「放量」上攻
    mybatis-plus中wrapper的用法(详细)
    Linux进程 ----- 信号处理
  • 原文地址:https://blog.csdn.net/weixin_60484917/article/details/128010828