FZU 2082 过路费

题目链接：http://acm.fzu.edu.cn/problem.php?pid=2082

题意：

有n座城市，由n-1条路相连通，使得任意两座城市之间可达。每条路有过路费，要交过路费才能通过。每条路的过路费经常会更新，现问你，当前情况下，从城市a到城市b最少要花多少过路费。

操作有两种：

一. 0 a b，表示更新第a条路的过路费为b，1 <= a <= n-1 ；

二. 1 a b ，表示询问a到b最少要花多少过路费。

思路：

权值在边上的树链剖分+线段树单点更新+线段树成段询问

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <vector>
  6 #include <algorithm>
  7 using namespace std;
  8 #define maxn 50010
  9 #define lson l, m, rt<<1
 10 #define rson m+1, r, rt<<1|1
 11 int n, q, s;
 12 struct Node
 13 {
 14     int to;
 15     long long val;
 16     Node(int t, long long v)
 17     {
 18         to = t; val = v;
 19     }
 20     Node(){}
 21 };
 22 vector <Node> mp[maxn];
 23 struct Edge
 24 {
 25     int from, to;
 26     long long val;
 27 }e[maxn];
 28 int pos;
 29 int siz[maxn], dep[maxn], top[maxn], fa[maxn], son[maxn], w[maxn], fw[maxn];
 30 long long cnt[maxn<<2];
 31 void PushUp(int rt)
 32 {
 33     cnt[rt] = cnt[rt<<1] + cnt[rt<<1|1];
 34 }
 35 void build(int l, int r, int rt)
 36 {
 37     cnt[rt] = 0;
 38     if(l == r) return;
 39     int m = (l+r)>>1;
 40     build(lson);
 41     build(rson);
 42     PushUp(rt);
 43 }
 44 void update(int p, long long val, int l, int r, int rt)
 45 {
 46     if(l == r)
 47     {
 48         cnt[rt] = val; return;
 49     }
 50     int m = (l+r)>>1;
 51     if(p <= m) update(p, val, lson);
 52     else update(p, val, rson);
 53     PushUp(rt);
 54 }
 55 long long query(int L, int R, int l, int r, int rt)
 56 {
 57     if(L <= l && R >= r)
 58     {
 59         return cnt[rt];
 60     }
 61     long long ret = 0;
 62     int m = (l+r)>>1;
 63     if(L <= m) ret += query(L, R, lson);
 64     if(R > m) ret += query(L, R, rson);
 65     return ret;
 66 }
 67 int dfs1(int u, int pre, int deep)
 68 {
 69     siz[u] = 1; fa[u] = pre; dep[u] = deep;
 70     int mmax = 0;
 71     for(int i = 0; i < mp[u].size(); i++)
 72     {
 73         if(mp[u][i].to != pre)
 74         {
 75             int temp = dfs1(mp[u][i].to, u, deep+1);
 76             siz[u] += temp;
 77             if(son[u] == -1 || temp >= mmax) son[u] = mp[u][i].to;        
 78         }
 79     }
 80     return siz[u];
 81 }
 82 void dfs2(int u, int val)
 83 {
 84     top[u] = val;
 85     if(son[u] != -1)
 86     {
 87         w[u] = pos++;
 88         fw[w[u]] = u;
 89         dfs2(son[u], val);
 90     }
 91     else if(son[u] == -1)
 92     {
 93         w[u] = pos++;
 94         fw[w[u]] = u;
 95         return;
 96     }
 97     for(int i = 0; i < mp[u].size(); i++)
 98     {
 99         if(mp[u][i].to != fa[u] && mp[u][i].to != son[u]) dfs2(mp[u][i].to, mp[u][i].to);
100     }
101 }
102 long long find(int u, int v)
103 {
104     int f1 = top[u], f2 = top[v];
105     long long temp = 0;
106     while(f1 != f2)
107     {
108         if(dep[f1] < dep[f2])
109         {
110             swap(f1, f2);
111             swap(u, v);
112         }
113         temp += query(w[f1], w[u], 1, pos-1, 1);
114         u = fa[f1]; f1 = top[u];
115     }
116     if(u == v) return temp;
117     if(dep[u] > dep[v]) swap(u, v);
118     temp += query(w[son[u]], w[v], 1, pos-1, 1);
119     return temp;
120 }
121 int main() 
122 {
123   // freopen("in.txt", "r", stdin);
124    //freopen("out.txt", "w", stdout);
125     while(~scanf("%d%d", &n, &q))
126     {
127         for(int i = 1; i <= n; i++) mp[i].clear();
128         pos = 0; memset(son, -1, sizeof(son));
129         
130         for(int i = 1; i <= n-1; i++)
131         {
132             scanf("%d%d%lld", &e[i].from, &e[i].to, &e[i].val);
133             mp[e[i].from].push_back(Node(e[i].to, e[i].val));
134             mp[e[i].to].push_back(Node(e[i].from, e[i].val));
135         }
136         dfs1(1, -1, 1);
137         dfs2(1, 1);
138         build(1, pos-1, 1);
139         
140         for(int i = 1; i <= n-1; i++)
141         {
142             if(dep[e[i].from] > dep[e[i].to])
143             {
144                 swap(e[i].from, e[i].to);
145             }
146             update(w[e[i].to], e[i].val, 1, pos-1, 1);
147         }
148         while(q--)
149         {
150             int op; scanf("%d", &op);
151             if(op == 1)
152             {
153                 //int u; scanf("%d", &u);
154                 int a, b; scanf("%d%d", &a, &b);
155                 printf("%lld
", find(a, b));
156             }
157             else if(op == 0)
158             {
159                 int i;
160                 long long ww; scanf("%d%lld", &i, &ww);
161                 update(w[e[i].to], ww, 1, pos-1, 1);
162             }
163         }
164     }
165     return 0;
166 }