Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // HOC HANH NHU CAI DAU KHAC
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <unordered_map>
- #include <set>
- #include <map>
- #define task "TESTs"
- using namespace std;
- using ll = long long;
- using ld = long double;
- const int N = 2e5 + 3;
- vector<pair<int, ll>> adj[N];
- int now[N], then[N];
- int n, m, l, q;
- int a[N], b[N];
- int par[20][N];
- int ranks[N];
- int last[N];
- ll st[N], z[N], d[N];
- void Read(){
- cin >> n >> q;
- for(int i = 1; i < n; ++i){
- ll c;
- cin >> a[i] >> b[i] >> z[i];
- adj[a[i]].push_back({b[i], z[i]});
- adj[b[i]].push_back({a[i], z[i]});
- }
- }
- /// --- DFS DECOMPOSITION --- ///
- /// - Ft. LCA - ///
- void dfs(int v){
- now[v] = ++m;
- then[m] = v;
- last[now[v]] = now[v];
- for(auto i : adj[v]){
- if(ranks[i.first] != 0)
- continue;
- ranks[i.first] = ranks[v] + 1;
- d[i.first] = d[v] + i.second;
- par[0][i.first] = v;
- dfs(i.first);
- last[now[v]] = max(last[now[v]], last[now[i.first]]);
- }
- }
- void LCA(){
- for(int i = 1; i <= 18; ++i)
- for(int j = 1; j <= n; ++j)
- par[i][j] = par[i - 1][par[i - 1][j]];
- }
- int find_par(int u, int v){
- if(ranks[u] < ranks[v])
- swap(u, v);
- for(int i = 18; ~i; --i)
- if(par[i][u] > 0 && ranks[par[i][u]] >= ranks[v])
- u = par[i][u];
- if(u == v)
- return u;
- for(int i = 18; ~i; --i)
- if(par[i][u] != par[i][v]){
- u = par[i][u];
- v = par[i][v];
- }
- while(u != v)
- u = par[0][u],
- v = par[0][v];
- return u;
- }
- void upd(int pos, ll v){
- for(int i = pos; i <= n; i += i & -i)
- st[i] += v;
- }
- ll que(int pos){
- ll ans = 0;
- for(int i = pos; i > 0; i -= i & -i)
- ans += st[i];
- return ans;
- }
- void Solve(){
- while(q--){
- int t;
- cin >> t;
- if(t == 1){
- int i;
- ll x;
- cin >> i >> x;
- int beg = max(now[a[i]], now[b[i]]);
- int en = last[beg];
- upd(beg, x - z[i]);
- upd(en + 1, z[i] - x);
- z[i] = x;
- }
- else{
- int u, v;
- cin >> u >> v;
- ll ans = 0;
- int h = find_par(u, v);
- cout << que(now[u]) + d[u] + que(now[v]) + d[v] - 2ll * (que(now[h]) + d[h]) << "\n";
- }
- }
- }
- main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);if(fopen(task".INP", "r"))
- freopen(task".INP", "r", stdin),
- freopen(task".OUT", "w", stdout);
- Read();
- ranks[1] = 1;
- dfs(1);
- LCA();
- Solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment