【FOJ】2082 过路费

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<iostream>
  5 #define MAXN 50010
  6 #define MAXM 100010
  7 using namespace std;
  8 int first[MAXN], next[MAXM], v[MAXM], cost[MAXM], e;
  9 bool vis[MAXN];
 10 struct LCT {
 11     int bef[MAXN], belong[MAXN];
 12     int next[MAXN][2], pre[MAXN], key[MAXN], sum[MAXN];
 13     void Init() {
 14         memset(next, 0, sizeof(next));
 15         memset(pre, 0, sizeof(pre));
 16     }
 17     inline void PushUp(int x) {
 18         sum[x] = key[x] + sum[next[x][0]] + sum[next[x][1]];
 19     }
 20     inline void Rotate(int x, int kind) {
 21         int y, z;
 22         y = pre[x];
 23         z = pre[y];
 24         next[y][!kind] = next[x][kind];
 25         pre[next[x][kind]] = y;
 26         next[z][next[z][1] == y] = x;
 27         pre[x] = z;
 28         next[x][kind] = y;
 29         pre[y] = x;
 30         PushUp(y);
 31     }
 32     void Splay(int x) {
 33         int rt;
 34         for (rt = x; pre[rt]; rt = pre[rt])
 35             ;
 36         if (rt != x) {
 37             bef[x] = bef[rt];
 38             bef[rt] = 0;
 39             while (pre[x]) {
 40                 if (next[pre[x]][0] == x)
 41                     Rotate(x, 1);
 42                 else
 43                     Rotate(x, 0);
 44             }
 45             PushUp(x);
 46         }
 47     }
 48     void Access(int x) {
 49         int father;
 50         for (father = 0; x; x = bef[x]) {
 51             Splay(x);
 52             pre[next[x][1]] = 0;
 53             bef[next[x][1]] = x;
 54             next[x][1] = father;
 55             pre[father] = x;
 56             bef[father] = 0;
 57             father = x;
 58             PushUp(x);
 59         }
 60     }
 61     void Change(int x, int val) {
 62         int t;
 63         t = belong[x - 1];
 64         key[t] = val;
 65         Splay(t);
 66     }
 67     int Query(int x, int y) {
 68         Access(y);
 69         for (y = 0; x; x = bef[x]) {
 70             Splay(x);
 71             if (!bef[x])
 72                 return sum[y] + sum[next[x][1]];
 73             pre[next[x][1]] = 0;
 74             bef[next[x][1]] = x;
 75             next[x][1] = y;
 76             pre[y] = x;
 77             bef[y] = 0;
 78             y = x;
 79             PushUp(x);
 80         }
 81         return 0;
 82     }
 83 } lct;
 84 int INT() {
 85     char ch;
 86     int res;
 87     while (ch = getchar(), !isdigit(ch))
 88         ;
 89     for (res = ch - '0'; ch = getchar(), isdigit(ch);)
 90         res = res * 10 + ch - '0';
 91     return res;
 92 }
 93 inline void AddEdge(int x, int y, int val) {
 94     v[e] = y;
 95     cost[e] = val;
 96     next[e] = first[x];
 97     first[x] = e++;
 98 }
 99 void BFS(int x) {
100     int i, y;
101     queue<int> q;
102     memset(vis, false, sizeof(vis));
103     vis[x] = true;
104     q.push(x);
105     while (!q.empty()) {
106         x = q.front();
107         q.pop();
108         for (i = first[x]; i != -1; i = next[i]) {
109             y = v[i];
110             if (!vis[y]) {
111                 lct.bef[y] = x;
112                 lct.key[y] = lct.sum[y] = cost[i];
113                 lct.belong[i >> 1] = y;
114                 vis[y] = true;
115                 q.push(y);
116             }
117         }
118     }
119 }
120 int main() {
121     int n, m;
122     int u, v, w;
123     while (~scanf("%d%d", &n, &m)) {
124         lct.Init();
125         memset(first, -1, sizeof(first));
126         for (e = 0; --n;) {
127             u = INT(), v = INT(), w = INT();
128             AddEdge(u, v, w);
129             AddEdge(v, u, w);
130         }
131         BFS(1);
132         while (m--) {
133             w = INT(), u = INT(), v = INT();
134             if (w == 0)
135                 lct.Change(u, v);
136             else
137                 printf("%d\n", lct.Query(u, v));
138         }
139     }
140     return 0;
141 }