樹鏈剖分基礎題
#include#include #include using namespace std; const int maxn = 10010; struct edge { int v, next; }e[maxn*2]; int first[maxn], cnt; int top[maxn], dep[maxn], sz[maxn], f[maxn], son[maxn], rank[maxn], tid[maxn]; int tp, tim; int d[maxn][3]; int n; void AddEdge(int u, int v) { e[cnt].v = v; e[cnt].next = first[u]; first[u] = cnt++; e[cnt].v = u; e[cnt].next = first[v]; first[v] = cnt++; } void init() { memset(first, -1, sizeof(first)); cnt = 1; memset(son, -1, sizeof(son)); tim = 0; } void dfs1(int u, int fa, int d) { sz[u] = 1; dep[u] = d; f[u] = fa; for(int i = first[u]; i != -1; i = e[i].next) { int v = e[i].v; if(v == fa) continue; dfs1(v, u, d+1); sz[u] += sz[v]; if(son[u] == -1 || sz[son[u]] < sz[v]) son[u] = v; } } void dfs2(int u, int tp) { top[u] = tp; tid[u] = ++tim; rank[tid[u]] = u; if(son[u] == -1) return; dfs2(son[u], tp); for(int i = first[u]; i != -1; i = e[i].next) { int v = e[i].v; if(v != f[u] && son[u] != v) dfs2(v, v); } } int ma[maxn<<2]; int mi[maxn<<2]; int lz[maxn<<2]; void pushup(int l, int r, int rt) { ma[rt] = max(ma[rt<<1], ma[rt<<1|1]); mi[rt] = min(mi[rt<<1], mi[rt<<1|1]); } void build(int l, int r, int rt) { ma[rt] = 0; mi[rt] = 0; lz[rt] = 0; if(l == r) { return; } int m = (l + r) >> 1; build(l, m, rt<<1); build(m+1, r, rt<<1|1); } void pushdown(int l, int r, int rt) { if(l == r) return; if(lz[rt]) { mi[rt<<1] = -mi[rt<<1]; ma[rt<<1] = -ma[rt<<1]; swap(mi[rt<<1], ma[rt<<1]); mi[rt<<1|1] = -mi[rt<<1|1]; ma[rt<<1|1] = -ma[rt<<1|1]; swap(mi[rt<<1|1], ma[rt<<1|1]); lz[rt<<1] ^= 1; lz[rt<<1|1] ^= 1; lz[rt] = 0; } } void update(int x, int y, int l, int r, int rt) { if(x == l && y == r) { mi[rt] = -mi[rt]; ma[rt] = -ma[rt]; swap(mi[rt], ma[rt]); lz[rt] ^= 1; return; } pushdown(l, r, rt); int m = (l + r) >> 1; if(y <= m) update(x, y, l, m, rt<<1); else if(x > m) update(x, y, m+1, r, rt<<1|1); else { update(x, m, l, m, rt<<1); update(m+1, y, m+1, r, rt<<1|1); } pushup(l, r, rt); } void update2(int x, int l, int r, int rt, int w) { if(l == r) { ma[rt] = mi[rt] = w; lz[rt] = 0; return; } pushdown(l, r, rt); int m = (l + r) >> 1; if(x <= m) update2(x, l, m, rt<<1, w); else update2(x, m+1, r, rt<<1|1, w); pushup(l, r, rt); } int query(int x, int y, int l, int r, int rt) { if(l == x && r == y) return ma[rt]; pushdown(l, r, rt); int m = (l + r) >> 1; if(y <= m) return query(x, y, l, m, rt<<1); else if(x > m) return query(x, y, m+1, r, rt<<1|1); else { return max(query(x, m, l, m, rt<<1), query(m+1, y, m+1, r, rt<<1|1)); } } void change(int u, int v) { while(top[u] != top[v]) { if(dep[top[u]] < dep[top[v]]) swap(u, v); update(tid[top[u]], tid[u], 1, n, 1); u = f[top[u]]; } if(u == v) return; if(dep[u] > dep[v]) swap(u, v); update(tid[son[u]], tid[v], 1, n, 1); } int find(int u, int v) { int ans = -999999999; while(top[u] != top[v]) { if(dep[top[u]] < dep[top[v]]) swap(u, v); ans = max(ans, query(tid[top[u]], tid[u], 1, n, 1)); u = f[top[u]]; } if(u == v) return ans; if(dep[u] > dep[v]) swap(u, v); ans = max(ans, query(tid[son[u]], tid[v], 1, n, 1)); return ans; } int main() { int T; scanf("%d", &T); while(T--) { init(); scanf("%d", &n); for(int i = 1; i < n; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); AddEdge(u, v); d[i][0] = u; d[i][1] = v; d[i][2] = w; } dfs1(1, 0, 0); dfs2(1, 1); build(1, n, 1); for(int i = 1; i < n; i++) { if(dep[d[i][0]] > dep[d[i][1]]) swap(d[i][0], d[i][1]); update2(tid[d[i][1]], 1, n, 1, d[i][2]); } char s[10]; while(scanf("%s", s) && strcmp(s, "DONE")) { if(s[0] == 'Q') { int x, y; scanf("%d %d", &x, &y); printf("%d\n", find(x, y)); } else if(s[0] == 'C') { int x, y; scanf("%d %d", &x, &y); update2(tid[d[x][1]], 1, n, 1, y); } else { int x, y; scanf("%d %d", &x, &y); change(x, y); } } } return 0; }
