树链剖分
捡起来好久没写的树剖。。。竟然没有写挂。。一次过了。。。
就是用线段树来维护一颗树上的dfs序#include#define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)using namespace std;typedef long long ll;inline int lowbit(int x){ return x & (-x); }inline int read(){ int X = 0, w = 0; char ch = 0; while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); } while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar(); return w ? -X : X;}inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }inline int lcm(int a, int b){ return a / gcd(a, b) * b; }template inline T max(T x, T y, T z){ return max(max(x, y), z); }template inline T min(T x, T y, T z){ return min(min(x, y), z); }template inline A fpow(A x, B p, C lyd){ A ans = 1; for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd; return ans;}const int N = 30005;int n, cnt, dfn, head[N], depth[N], size[N], son[N], p[N], top[N], id[N], w[N], val[N];int tree[N<<2], m[N<<2];struct Edge { int v, next; } edge[N<<1];void addEdge(int a, int b){ edge[cnt].v = b, edge[cnt].next = head[a], head[a] = cnt ++;}void dfs1(int s, int fa){ depth[s] = depth[fa] + 1; p[s] = fa; size[s] = 1; int child = -1; for(int i = head[s]; i != -1; i = edge[i].next){ int u = edge[i].v; if(u == fa) continue; dfs1(u, s); size[s] += size[u]; if(size[u] > child) child = size[u], son[s] = u; }}void dfs2(int s, int tp){ id[s] = ++dfn; w[id[s]] = val[s]; top[s] = tp; if(son[s] != -1) dfs2(son[s], tp); for(int i = head[s]; i != -1; i = edge[i].next){ int u = edge[i].v; if(u == p[s] || u == son[s]) continue; dfs2(u, u); }}void push_up(int rt){ tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]; m[rt] = max(m[rt << 1], m[rt << 1 | 1]);}void buildTree(int rt, int l, int r){ if(l == r){ tree[rt] = m[rt] = w[l]; return; } int mid = (l + r) >> 1; buildTree(rt << 1, l, mid); buildTree(rt << 1 | 1, mid + 1, r); push_up(rt);}void modify(int rt, int l, int r, int k, int t){ if(l == r){ tree[rt] = m[rt] = t; return; } int mid = (l + r) >> 1; if(k <= mid) modify(rt << 1, l, mid, k, t); else modify(rt << 1 | 1, mid + 1, r, k, t); push_up(rt);}int queryMax(int rt, int l, int r, int queryL, int queryR){ if(l == queryL && r == queryR){ return m[rt]; } int mid = (l + r) >> 1; if(queryL > mid) return queryMax(rt << 1 | 1, mid + 1, r, queryL, queryR); else if(queryR <= mid) return queryMax(rt << 1, l, mid, queryL, queryR); else return max(queryMax(rt << 1, l, mid, queryL, mid), queryMax(rt << 1 | 1, mid + 1, r, mid + 1, queryR));}int querySum(int rt, int l, int r, int queryL, int queryR){ if(l == queryL && r == queryR){ return tree[rt]; } int mid = (l + r) >> 1; if(queryL > mid) return querySum(rt << 1 | 1, mid + 1, r, queryL, queryR); else if(queryR <= mid) return querySum(rt << 1, l, mid, queryL, queryR); else return querySum(rt << 1, l, mid, queryL, mid) + querySum(rt << 1 | 1, mid + 1, r, mid + 1, queryR);}int treeMax(int x, int y){ int ret = -INF; while(top[x] != top[y]){ if(depth[top[x]] < depth[top[y]]) swap(x, y); ret = max(ret, queryMax(1, 1, n, id[top[x]], id[x])); x = p[top[x]]; } if(depth[x] > depth[y]) swap(x, y); return max(ret, queryMax(1, 1, n, id[x], id[y]));}int treeSum(int x, int y){ int ret = 0; while(top[x] != top[y]){ if(depth[top[x]] < depth[top[y]]) swap(x, y); ret += querySum(1, 1, n, id[top[x]], id[x]); x = p[top[x]]; } if(depth[x] > depth[y]) swap(x, y); ret += querySum(1, 1, n, id[x], id[y]); return ret;}int main(){ full(head, -1); full(son, -1); n = read(); for(int i = 0; i < n - 1; i ++){ int u = read(), v = read(); addEdge(u, v), addEdge(v, u); } for(int i = 1; i <= n; i ++) val[i] = read(); dfs1(1, 0), dfs2(1, 1); buildTree(1, 1, n); int q = read(); while(q --){ char opt[10]; scanf("%s", opt); if(opt[1] == 'H'){ int x = read(), y = read(); modify(1, 1, n, id[x], y); } else if(opt[1] == 'M'){ int x = read(), y = read(); printf("%d\n", treeMax(x, y)); } else if(opt[1] == 'S'){ int x = read(), y = read(); printf("%d\n", treeSum(x, y)); } } return 0;}