Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- #define endl "\n"
- using namespace std;
- vector<vector<int>> gr;
- int timer;
- vector<int> t, tin, tout;
- void dfs(int v, int pr = -1) {
- tin[v] = timer;
- for(auto it: gr[v]) {
- if(it != pr) {
- timer++;
- dfs(it, v);
- }
- }
- tout[v] = timer;
- }
- void update(int v, int tl, int tr, int pos, int val) {
- if(tl == tr) {
- t[v] += val;
- } else {
- int tm = (tl + tr) / 2;
- if(pos <= tm) {
- update(v + v, tl, tm, pos, val);
- } else {
- update(v + v + 1, tm + 1, tr, pos, val);
- }
- t[v] = t[v + v] + t[v + v + 1];
- }
- }
- int get(int v, int tl, int tr, int l, int r) {
- if(l > r) return 0;
- if(tl == l && tr == r) {
- return t[v];
- } else {
- int tm = (tl + tr) /2 ;
- return get(v + v, tl, tm, l, min(r, tm)) + get(v + v + 1, tm + 1, tr, max(l, tm + 1), r);
- }
- }
- void solve() {
- int n, q;
- cin >> n >> q;
- gr = vector<vector<int>> (n + 1, vector<int> ());
- tin = tout = vector<int> (n + 1);
- timer = 1;
- for(int i = 1; i < n; i++) {
- int l, r;
- cin >> l >> r;
- gr[l].push_back(r);
- gr[r].push_back(l);
- }
- dfs(1);
- t = vector<int> (4 * n + 4);
- while(q--) {
- int a, b, x;
- cin >> a >> b >> x;
- if(!x) {
- if(tin[a] < tin[b]) {
- swap(a, b);
- }
- cout << abs(get(1, 1, n, tin[a], tout[a])) << endl;
- } else {
- update(1, 1, n, tin[a], x);
- update(1, 1, n, tin[b], -x);
- }
- }
- }
- main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int t;
- cin >> t;
- while(t--) {
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement