题面：给定一个有$n$个节点的树，每个点又点权$v_i$，每次选取一条树链$[a, b]$，求出$max(v_i - v_j)$，其中$i, j in [a, b]$且$i$出现在$j$前面，最后树链$[a, b]$上的点点权都加上$v'$
裸的树链剖分，用线段树维护树链。。。查询的时候要用线段树合并。。。然后就没有然后了。。。
代码能力捉鸡QAQQQ，而且貌似是C++程序里面跑的最慢的QAQQQ
1 /************************************************************** 2 Problem: 3999 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:4268 ms 7 Memory:17988 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <algorithm> 12 13 using namespace std; 14 typedef long long ll; 15 const int N = 5e4 + 5; 16 const int inf = 1e9; 17 18 inline int read(); 19 20 int n; 21 int a[N], seq[N], cnt_seq; 22 23 struct edge { 24 int next, to; 25 edge() {} 26 edge(int _n, int _t) : next(_n), to(_t) {} 27 } e[N << 1]; 28 29 int first[N], tot; 30 31 struct tree_node { 32 int sz, dep, fa, son, v; 33 int top, pos; 34 } tr[N]; 35 36 struct seg { 37 seg *ls, *rs, *res; 38 ll mx, mn, mxl, mxr, tag; 39 40 #define Len (1 << 16) 41 inline void* operator new(size_t) { 42 static seg *mempool, *c; 43 if (mempool == c) 44 mempool = (c = new seg[Len]) + Len; 45 return c++; 46 } 47 #undef Len 48 inline seg& operator += (int x) { 49 mx += x, mn += x, tag += x; 50 } 51 52 inline seg* rev() { 53 swap(mxl, mxr); 54 return this; 55 } 56 inline void update(seg *ls, seg *rs) { 57 mxl = max(max(ls -> mxl, rs -> mxl), ls -> mx - rs -> mn); 58 mxr = max(max(ls -> mxr, rs -> mxr), rs -> mx - ls -> mn); 59 mx = max(ls -> mx, rs -> mx), mn = min(ls -> mn, rs -> mn); 60 } 61 inline void push() { 62 if (tag) { 63 *ls += tag, *rs += tag; 64 tag = 0; 65 } 66 } 67 68 #define mid (l + r >> 1) 69 inline void build(int l, int r, int* a) { 70 res = new()seg; 71 if (l == r) { 72 mx = mn = a[l]; 73 return; 74 } 75 ls = new()seg(), rs = new()seg; 76 ls -> build(l, mid, a), rs -> build(mid + 1, r, a); 77 update(ls, rs); 78 } 79 80 inline void add(int l, int r, int L, int R, int d) { 81 if (L <= l && r <= R) { 82 *this += d; 83 return; 84 } 85 push(); 86 if (L <= mid) ls -> add(l, mid, L, R, d); 87 if (mid < R) rs -> add(mid + 1, r, L, R, d); 88 update(ls, rs); 89 } 90 91 inline seg* query(int l, int r, int L, int R) { 92 if (L <= l && r <= R) { 93 *res = *this; 94 return res; 95 } 96 *res = seg(), push(); 97 if (mid >= R) res = ls -> query(l, mid, L, R); 98 else if (mid < L) res = rs -> query(mid + 1, r, L, R); 99 else res -> update(ls -> query(l, mid, L, R), rs -> query(mid + 1, r, L, R)); 100 update(ls, rs); 101 return res; 102 } 103 #undef mid 104 } *T; 105 106 inline void get(seg *t, int f, int a, int b, int v) { 107 if (!f) t -> update(T -> query(1, n, a, b), t); 108 else t -> update(t, T -> query(1, n, a, b) -> rev()); 109 T -> add(1, n, a, b, v); 110 } 111 112 inline void pre(seg *t) { 113 *t = seg(); 114 t -> mx = t -> mxl = t -> mxr = -inf, t -> mn = inf; 115 } 116 117 inline void work(int x, int y, int v) { 118 static seg *left = new()seg, *right = new()seg, *ans = new()seg; 119 pre(left), pre(right); 120 while (tr[x].top != tr[y].top) { 121 if (tr[tr[x].top].dep > tr[tr[y].top].dep) 122 get(right, 0, tr[tr[x].top].pos, tr[x].pos, v), x = tr[tr[x].top].fa; 123 else 124 get(left, 1, tr[tr[y].top].pos, tr[y].pos, v), y = tr[tr[y].top].fa; 125 } 126 if (tr[x].dep > tr[y].dep) get(right, 0, tr[y].pos, tr[x].pos, v); 127 else get(left, 1, tr[x].pos, tr[y].pos, v); 128 ans -> update(left, right); 129 printf("%lld ", max(ans -> mxl, 0ll)); 130 } 131 132 inline void Add_Edges(int x, int y) { 133 e[++tot] = edge(first[x], y), first[x] = tot; 134 e[++tot] = edge(first[y], x), first[y] = tot; 135 } 136 137 #define y e[x].to 138 void dfs(int p) { 139 int x; 140 tr[p].sz = 1; 141 for (x = first[p]; x; x = e[x].next) 142 if (y != tr[p].fa) { 143 tr[y].fa = p, tr[y].dep = tr[p].dep + 1; 144 dfs(y); 145 tr[p].sz += tr[y].sz; 146 if (!tr[p].son || tr[tr[p].son].sz < tr[y].sz) tr[p].son = y; 147 } 148 } 149 150 void DFS(int p) { 151 int x; 152 seq[tr[p].pos = ++cnt_seq] = tr[p].v; 153 if (!tr[p].son) return; 154 tr[tr[p].son].top = tr[p].top; 155 DFS(tr[p].son); 156 for (x = first[p]; x; x = e[x].next) 157 if (y != tr[p].fa && y != tr[p].son) 158 tr[y].top = y, DFS(y); 159 } 160 #undef y 161 162 int main() { 163 int i, x, y, z, Q; 164 n = read(); 165 for (i = 1; i <= n; ++i) tr[i].v = read(); 166 for (i = 1; i < n; ++i) 167 Add_Edges(read(), read()); 168 dfs(1); 169 tr[1].top = 1, DFS(1); 170 T = new()seg; 171 T -> build(1, n, seq); 172 for (Q = read(); Q; --Q) { 173 x = read(), y = read(), z = read(); 174 work(x, y, z); 175 } 176 return 0; 177 } 178 179 inline int read() { 180 static int x; 181 static char ch; 182 x = 0, ch = getchar(); 183 while (ch < '0' || '9' < ch) 184 ch = getchar(); 185 while ('0' <= ch && ch <= '9') { 186 x = x * 10 + ch - '0'; 187 ch = getchar(); 188 } 189 return x; 190 }