Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //CODECHEF TAQTREE
- #include <bits/stdc++.h>
- using namespace std;
- int n,q;
- vector<int> v[100001], w[100001];
- struct edge{
- int U, V, W;
- }e[100001];
- ////////////////////////////////////////////LCA part
- const int bnd = 18;//the max(logn)
- int F[100001][bnd];//lca form
- int depth[100001];
- void make(int d, int u, int pre){
- depth[u] = d;
- F[u][0] = pre;
- for(int i = 1; i < bnd; ++i)F[u][i] = F[F[u][i-1]][i-1];
- for(int i = 0; i < v[u].size(); ++i){
- if(v[u][i] != pre)make(d+1, v[u][i], u);
- }
- }
- int lca(int u, int v){
- if(depth[u] > depth[v])swap(u, v);//make sure depth[u] <= depth[v]
- for(int i = bnd-1; i >= 0 && depth[u] != depth[v]; --i){
- if(depth[v] - depth[u] >= (1<<i))v = F[v][i];
- }
- if(u == v)return u;
- for(int i = bnd-1; i >= 0; --i){
- if(F[u][i] != F[v][i]){
- u = F[u][i];
- v = F[v][i];
- }
- }
- return F[u][0];
- }
- ////////////////////////////////////////////BIT part
- int BIT[200001];
- void addv(int k, int val){//change the value at node (k)
- while(k <= 2*n){
- BIT[k] += val;
- k += (k & -k);
- }
- }
- int getv(int k){//get distance from node (k) to node (1)
- int ret = 0;
- while(k){
- ret += BIT[k];
- k -= (k & -k);
- }
- return ret;
- }
- ////////////////////////////////////////////DFS part
- //using euler traversal
- int cnt = 0;
- int in[100001], out[100001];//dfs orders
- void dfs(int u, int pre, int val){//val is the weight to parent
- in[u] = ++cnt;
- addv(in[u], val);
- for(int i = 0; i < v[u].size(); ++i){
- if(v[u][i] != pre)dfs(v[u][i], u, w[u][i]);
- }
- out[u] = ++cnt;
- addv(out[u], -val);
- }
- ////////////////////////////////////////////main part
- int32_t main(){
- cin >> n;
- for(int i = 1; i < n; ++i){
- int a,b,c;
- cin >> a >> b >> c;
- v[a].emplace_back(b);
- v[b].emplace_back(a);
- w[a].emplace_back(c);
- w[b].emplace_back(c);
- e[i] = {.U = a, .V = b, .W = c};
- }
- dfs(1, 0, 0);//root = 1, parent = 0, weight to parent = 0
- make(1, 1, 0);//root depth = 1, root = 1, parent = 0
- cin >> q;
- while(q--){
- int a,b,c;
- cin >> a >> b >> c;
- if(a == 1){
- int addw = c - e[b].W;
- if(depth[e[b].U] > depth[e[b].V])swap(e[b].U, e[b].V);
- addv(in[e[b].V], addw);
- addv(out[e[b].V], -addw);
- }else if(a == 2){
- int parent = lca(b, c);
- cout << getv(in[b]) + getv(in[c]) - 2 * getv(in[parent]) << '\n';
- }
- }
- return 0;
- }
RAW Paste Data