Luogu 2912 [USACO08OCT]牧场散步Pasture Walking

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define rd read()
  5 #define lson nd << 1
  6 #define rson nd << 1 | 1
  7 using namespace std;
  8 
  9 const int N = 1e4;
 10 
 11 int dep[N], top[N], f[N], son[N], size[N], id[N];
 12 int q, n, head[N], tot, cnt, A[N], a[N];
 13 int sum[N << 2];
 14 
 15 struct edge {
 16     int nxt, to, val;
 17 }e[N << 1];
 18 
 19 int read() {
 20     int X = 0, p = 1; char c = getchar();
 21     for(; c > '9' || c < '0'; c = getchar()) if(c == '-') p = -1;
 22     for(; c >= '0' && c <= '9'; c = getchar()) X = X * 10 + c - '0';
 23     return X * p;
 24 }
 25 
 26 void added(int u, int v, int val) {
 27     e[++tot].to = v;
 28     e[tot].nxt = head[u];
 29     e[tot].val = val;
 30     head[u] = tot;
 31 }
 32 
 33 void add(int u, int v, int val) {
 34     added(u, v, val);
 35     added(v, u, val);
 36 }
 37 
 38 void dfs1(int u) {
 39     size[u] = 1;
 40     for(int i = head[u]; i; i = e[i].nxt) {
 41         int nt = e[i].to;
 42         if(nt == f[u]) continue;
 43         f[nt] = u; dep[nt] = dep[u] + 1;
 44         a[nt] = e[i].val;
 45         dfs1(nt);
 46         size[u] += size[nt];
 47         if(size[nt] > size[son[u]]) son[u] = nt;
 48     }
 49 }
 50 
 51 void dfs2(int u) {
 52     id[u] = ++cnt;
 53     A[cnt] = a[u];
 54     if(!son[u]) return;
 55     top[son[u]] = top[u];
 56     dfs2(son[u]);
 57     for(int i = head[u]; i; i = e[i].nxt) {
 58         int nt = e[i].to;
 59         if(nt == f[u] || nt == son[u]) continue;
 60         top[nt] = nt;
 61         dfs2(nt);
 62     }
 63 }
 64 
 65 void update(int nd) {
 66     sum[nd] = sum[lson] + sum[rson];
 67 }
 68 
 69 void build(int l, int r, int nd) {
 70     if(l == r) { sum[nd] = A[l]; return;}
 71     int mid = (l + r) >> 1;
 72     build(l, mid, lson);
 73     build(mid + 1, r, rson);
 74     update(nd);
 75 }
 76 
 77 int trie_sum(int L, int R, int l, int r, int nd) {
 78     if(L <= l && r <= R) return sum[nd];
 79     int tmp = 0, mid = (l + r) >> 1;
 80     if(L <= mid) tmp += trie_sum(L, R, l, mid, lson);
 81     if(mid < R) tmp += trie_sum(L, R, mid + 1, r, rson);
 82     return tmp;
 83 }
 84 
 85 void sw(int &x, int &y) {
 86     x ^= y, y ^= x, x ^= y;
 87 }
 88 
 89 int query(int x, int y) {
 90     int ans = 0, tmp;
 91     for(; top[x] != top[y];) {
 92         if(dep[top[x]] < dep[top[y]]) swap(x, y);
 93         tmp = trie_sum(id[top[x]], id[x], 1, n, 1);
 94         ans += tmp;
 95         x = f[top[x]];
 96     }
 97     if(dep[x] < dep[y]) swap(x, y);
 98     tmp = trie_sum(id[y], id[x], 1, n, 1);
 99     ans += tmp - a[y];
100     return ans;
101 }
102 
103 int main()
104 {
105     n = rd; q = rd;
106     for(int i = 1; i < n; ++i) {
107         int x = rd, y = rd, z = rd;
108         add(x, y, z);
109     }
110     dfs1(1); dfs2(1);
111     build(1, n, 1);
112     for(; q; q--) {
113         int x = rd, y = rd;
114         printf("%d
", query(x, y));
115     }
116 }