#include <cstdio> #include <cstring> #include <iostream> #include <cmath> #include <algorithm> #include <vector> using namespace std; const int maxv = 1e5+10; typedef long long ll; int a[maxv], b[maxv], weight[maxv]; int n, q, s; int type[maxv]; int x[maxv], t[maxv]; int root; int vs[maxv*2]; int depth[maxv*2]; int id[maxv]; int es[maxv*2]; struct Edge{ int id, to, cost; }; vector<Edge> G[maxv]; ll c[maxv*2]; void add(int i, int val){ while(i<=maxv*2){ c[i] += val; i += i&(-i); } } int sum(int i){ ll ans = 0; while(i>0){ ans += c[i]; i -= i&(-i); } return ans; } void dfs(int v, int p, int d, int& k){ id[v] = k; vs[k] = v; depth[k++] = d; for(int i=0; i<G[v].size(); i++){ Edge &e = G[v][i]; if(e.to!=p){ add(k, e.cost); es[e.id*2] = k; dfs(e.to, v, d+1, k); vs[k] = v; depth[k++] = d; add(k, -e.cost); es[e.id*2+1] = k; } } } int d[maxv*2][21]; int min_index(int i, int j){ return depth[i]<depth[j]?i:j; } void rmq_init(int n){ for(int i=0; i<n; i++){ d[i][0] = i; } for(int j=1; (1<<j)<=n; j++){ for(int i=0; (i+(1<<j))<n; i++){ d[i][j] = min_index(d[i][j-1], d[i+(1<<(j-1))][j-1]); } } } int query(int l ,int r){ int k = floor(log2(r-l+1)); return min_index(d[l][k], d[r-(1<<k)+1][k]); } int lca(int u, int v){ int l = min(id[u], id[v]); int r = max(id[u], id[v]); int val = query(l, r); return vs[val]; } void init(int n){ int d = 0, k =0; dfs(root, -1, d, k); rmq_init(n*2-1); } void solve(){ root = n/2; for(int i=0; i<n-1; i++){ G[i].clear(); } for(int i=0; i<n-1; i++){ G[a[i]-1].push_back(Edge{i, b[i]-1, weight[i]}); G[b[i]-1].push_back(Edge{i, a[i]-1, weight[i]}); } init(n); int v = s-1; for(int i=0; i<q; i++){ if(type[i] == 0){ int u = x[i]-1; int p = lca(v, u); printf("%d\n", sum(id[v])+sum(id[u])-2*sum(id[p])); v = u; } else{ int k = x[i]-1; add(es[k*2], t[i]-weight[k]); add(es[k*2+1], weight[k]-t[i]); weight[k] = t[i]; } } } int main() { while(~scanf("%d%d%d", &n, &q, &s)){ for(int i=0; i<n-1; i++){ scanf("%d%d%d", &a[i], &b[i], &weight[i]); } memset(c, 0, sizeof(c)); for(int i=0; i<q; i++){ scanf("%d", &type[i]); if(type[i] == 0){ scanf("%d", &x[i]); } else{ scanf("%d%d", &x[i], &t[i]); } } solve(); } return 0; }
|