POJ 2763 Housewife Wind

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 const int maxn = 100010;
  7 struct arc{
  8     int to,w,next;
  9     arc(int x = 0,int y = 0,int z = -1){
 10         to = x;
 11         w = y;
 12         next = z;
 13     }
 14 }e[maxn<<1];
 15 struct node{
 16     int lt,rt,sum;
 17 }tree[maxn<<2];
 18 int head[maxn],fa[maxn],top[maxn],dep[maxn];
 19 int siz[maxn],son[maxn],loc[maxn];
 20 int n,q,s,tot,clk;
 21 void add(int u,int v,int w){
 22     e[tot] = arc(v,w,head[u]);
 23     head[u] = tot++;
 24 }
 25 void FindHeavyEdge(int u,int father,int depth){
 26     fa[u] = father;
 27     son[u] = -1;
 28     siz[u] = 1;
 29     dep[u] = depth;
 30     for(int i = head[u]; ~i; i = e[i].next){
 31         if(e[i].to == father) continue;
 32         FindHeavyEdge(e[i].to,u,depth + 1);
 33         siz[u] += siz[e[i].to];
 34         if(son[u] == -1 || siz[e[i].to] > siz[son[u]])
 35             son[u] = e[i].to;
 36     }
 37 }
 38 void ConnectHeavyEdge(int u,int ancestor){
 39     top[u] = ancestor;
 40     loc[u] = clk++;
 41     if(son[u] != -1) ConnectHeavyEdge(son[u],ancestor);
 42     for(int i = head[u]; ~i; i = e[i].next){
 43         if(e[i].to == fa[u] || son[u] == e[i].to) continue;
 44         ConnectHeavyEdge(e[i].to,e[i].to);
 45     }
 46 }
 47 void build(int lt,int rt,int v){
 48     tree[v].lt = lt;
 49     tree[v].rt = rt;
 50     tree[v].sum = 0;
 51     if(lt == rt) return;
 52     int mid = (lt + rt)>>1;
 53     build(lt,mid,v<<1);
 54     build(mid + 1,rt,v<<1|1);
 55 }
 56 void update(int pos,int val,int v){
 57     if(tree[v].lt == tree[v].rt){
 58         tree[v].sum = val;
 59         return;
 60     }
 61     if(pos <= tree[v<<1].rt) update(pos,val,v<<1);
 62     else update(pos,val,v<<1|1);
 63     tree[v].sum = tree[v<<1].sum + tree[v<<1|1].sum;
 64 }
 65 int query(int lt,int rt,int v){
 66     if(lt <= tree[v].lt && rt >= tree[v].rt)
 67         return tree[v].sum;
 68     int ret = 0;
 69     if(lt <= tree[v<<1].rt) ret = query(lt,rt,v<<1);
 70     if(rt >= tree[v<<1|1].lt) ret += query(lt,rt,v<<1|1);
 71     return ret;
 72 }
 73 int QUERY(int u,int v){
 74     if(u == v) return 0;
 75     int ret = 0;
 76     while(top[u] != top[v]){
 77         if(dep[top[u]] < dep[top[v]]) swap(u,v);
 78         ret += query(loc[top[u]],loc[u],1);
 79         u = fa[top[u]];
 80     }
 81     if(u == v) return ret;
 82     if(dep[u] > dep[v]) swap(u,v);
 83     ret += query(loc[son[u]],loc[v],1);
 84     return ret;
 85 }
 86 int main(){
 87     int u,v,w,op;
 88     while(~scanf("%d%d%d",&n,&q,&s)){
 89         memset(head,-1,sizeof head);
 90         tot = clk = 0;
 91         for(int i = 1; i < n; ++i){
 92             scanf("%d%d%d",&u,&v,&w);
 93             add(u,v,w);
 94             add(v,u,w);
 95         }
 96         FindHeavyEdge(1,0,0);
 97         ConnectHeavyEdge(1,1);
 98         build(0,clk-1,1);
 99         for(int i = 0; i < tot; i += 2){
100             u = e[i].to;
101             v = e[i + 1].to;
102             if(dep[u] < dep[v]) swap(u,v);
103             update(loc[u],e[i].w,1);
104         }
105         while(q--){
106             scanf("%d",&op);
107             if(op){
108                 scanf("%d%d",&u,&w);
109                 int ith = (u-1)*2;
110                 if(dep[e[ith].to] < dep[e[ith + 1].to]) ++ith;
111                 update(loc[e[ith].to],w,1);
112             }else{
113                 scanf("%d",&u);
114                 printf("%d\n",QUERY(s,u));
115                 s = u;
116             }
117         }
118     }
119     return 0;
120 }