二次联通门 : COGS 1583. [POJ3237]树的维护
/* COGS 1583. [POJ3237]树的维护 树链剖分 + 边权化点权 线段树 单点修改 + 区间取相反数 + 查询区间最大 对于区间取相反数 考虑在线段树中维护两个值 一个区间最大, 一个区间最小 对于更改, 只需把区间最大与最小分别取相反数后交换即可 然后对于标记, 由于对区间连续取反两次相当于不变 则只需开一个bool 标记, 每次放标记时对标记取反即可 */ #include <cstdio> #define INF 1e7 #define Max 20005 inline int max (int a, int b) { return a > b ? a : b; } inline int min (int a, int b) { return a < b ? a : b; } inline int swap (int &a, int &b) { int now = a; a = b; b = now; } void read (int &now) { now = 0; bool temp = false; register char word = getchar (); while (word < '0' || word > '9') { if (word == '-') temp = true; word = getchar (); } while (word <= '9' && word >= '0') { now = now * 10 + word - '0'; word = getchar (); } } int tree_value[Max]; class Segment_Tree_Type { private : struct Tree_Date { int l; int r; int Maxn; int Minn; int Mid; bool Flandre_Scarlet; } tree[Max << 3]; public : void Build (int l, int r, int now) { tree[now].l = l; tree[now].r = r; if (l == r) { tree[now].Maxn = tree_value[l]; tree[now].Minn = tree_value[r]; return ; } tree[now].Mid = l + r >> 1; Build (l, tree[now].Mid, now << 1); Build (tree[now].Mid + 1, r, now << 1 | 1); tree[now].Maxn = max (tree[now << 1].Maxn, tree[now << 1 | 1].Maxn); tree[now].Minn = min (tree[now << 1].Minn, tree[now << 1 | 1].Minn); } int Query_Section (int l, int r, int now) { if (tree[now].l == l && tree[now].r == r) return tree[now].Maxn; if (tree[now].Flandre_Scarlet) { tree[now << 1].Maxn = -tree[now << 1].Maxn; tree[now << 1 | 1].Maxn = -tree[now << 1 | 1].Maxn; tree[now << 1].Minn = -tree[now << 1].Minn; tree[now << 1 | 1].Minn = -tree[now << 1 | 1].Minn; swap (tree[now << 1].Maxn, tree[now << 1].Minn); tree[now << 1].Flandre_Scarlet = !tree[now << 1].Flandre_Scarlet; swap (tree[now << 1 | 1].Maxn, tree[now << 1 | 1].Minn); tree[now << 1 | 1].Flandre_Scarlet = !tree[now << 1 | 1].Flandre_Scarlet; tree[now].Flandre_Scarlet = false; } tree[now].Maxn = max (tree[now << 1].Maxn, tree[now << 1 | 1].Maxn); tree[now].Minn = min (tree[now << 1].Minn, tree[now << 1 | 1].Minn); if (r <= tree[now].Mid) return Query_Section (l, r, now << 1); else if (l > tree[now].Mid) return Query_Section (l, r, now << 1 | 1); else return max (Query_Section (l, tree[now].Mid, now << 1), Query_Section (tree[now].Mid + 1, r, now << 1 | 1)); } void Change_Section (int l, int r, int now) { if (tree[now].l == l && tree[now].r == r) { tree[now].Maxn = -tree[now].Maxn; tree[now].Minn = -tree[now].Minn; swap (tree[now].Maxn, tree[now].Minn); tree[now].Flandre_Scarlet = !tree[now].Flandre_Scarlet; return ; } if (tree[now].Flandre_Scarlet) { tree[now << 1].Maxn = -tree[now << 1].Maxn; tree[now << 1 | 1].Maxn = -tree[now << 1 | 1].Maxn; tree[now << 1].Minn = -tree[now << 1].Minn; tree[now << 1 | 1].Minn = -tree[now << 1 | 1].Minn; swap (tree[now << 1].Maxn, tree[now << 1].Minn); tree[now << 1].Flandre_Scarlet = !tree[now << 1].Flandre_Scarlet; swap (tree[now << 1 | 1].Maxn, tree[now << 1 | 1].Minn); tree[now << 1 | 1].Flandre_Scarlet = !tree[now << 1 | 1].Flandre_Scarlet; tree[now].Flandre_Scarlet = false; } if (r <= tree[now].Mid) Change_Section (l, r, now << 1); else if (l > tree[now].Mid) Change_Section (l, r, now << 1 | 1); else { Change_Section (l, tree[now].Mid, now << 1); Change_Section (tree[now].Mid + 1, r, now << 1 | 1); } tree[now].Maxn = max (tree[now << 1].Maxn, tree[now << 1 | 1].Maxn); tree[now].Minn = min (tree[now << 1].Minn, tree[now << 1 | 1].Minn); } void Change_Single (int pos, int now, int number) { if (tree[now].l == tree[now].r) { tree[now].Maxn = number; tree[now].Minn = number; return; } if (tree[now].Flandre_Scarlet) { tree[now << 1].Maxn = -tree[now << 1].Maxn; tree[now << 1 | 1].Maxn = -tree[now << 1 | 1].Maxn; tree[now << 1].Minn = -tree[now << 1].Minn; tree[now << 1 | 1].Minn = -tree[now << 1 | 1].Minn; swap (tree[now << 1].Maxn, tree[now << 1].Minn); tree[now << 1].Flandre_Scarlet = !tree[now << 1].Flandre_Scarlet; swap (tree[now << 1 | 1].Maxn, tree[now << 1 | 1].Minn); tree[now << 1 | 1].Flandre_Scarlet = !tree[now << 1 | 1].Flandre_Scarlet; tree[now].Flandre_Scarlet = false; } if (pos <= tree[now].Mid) Change_Single (pos, now << 1, number); else Change_Single (pos, now << 1 | 1, number); tree[now].Maxn = max (tree[now << 1].Maxn, tree[now << 1 | 1].Maxn); tree[now].Minn = min (tree[now << 1].Minn, tree[now << 1 | 1].Minn); } }; Segment_Tree_Type Segment_Tree; class Tree_Chain_Type { private : struct Edge_Date { int to; int next; int key; int from; } edge[Max << 2]; struct Point_Date { int size; int father; int up_chain_point; int deep; int segment_tree_pos; } point[Max]; int Edge_Count; int edge_list[Max]; int Segment_Pos; int Count; public : inline int Add_Edge (int from, int to, int dis) { Edge_Count++; edge[Edge_Count].to = to; edge[Edge_Count].from = from; edge[Edge_Count].next = edge_list[from]; edge_list[from] = Edge_Count; edge[Edge_Count].key = dis; Edge_Count++; edge[Edge_Count].to = from; edge[Edge_Count].from = to; edge[Edge_Count].next = edge_list[to]; edge_list[to] = Edge_Count; edge[Edge_Count].key = dis; } void Dfs_1 (int now, int father) { int pos = Count++; point[now].father = father; point[now].deep = point[father].deep + 1; for (int i = edge_list[now]; i; i = edge[i].next) if (edge[i].to != father) Dfs_1 (edge[i].to, now); point[now].size = Count - pos; } void Dfs_2 (int now, int chain) { point[now].segment_tree_pos = ++Segment_Pos; for (int i = edge_list[now]; i; i = edge[i].next) if (edge[i].to == point[now].father) { tree_value[Segment_Pos] = edge[i].key; break; } point[now].up_chain_point = chain; int pos = 0; for (int i = edge_list[now]; i; i = edge[i].next) if (!point[edge[i].to].segment_tree_pos && point[edge[i].to].size > point[pos].size) pos = edge[i].to; if (!pos) return; Dfs_2 (pos, chain); for (int i = edge_list[now]; i; i = edge[i].next) if (!point[edge[i].to].segment_tree_pos && edge[i].to != pos) Dfs_2 (edge[i].to, edge[i].to); } int Query_chain (int x, int y) { int Answer = -INF; while (point[x].up_chain_point != point[y].up_chain_point) { if (point[point[x].up_chain_point].deep < point[point[y].up_chain_point].deep) swap (x, y); Answer = max (Answer, Segment_Tree.Query_Section (point[point[x].up_chain_point].segment_tree_pos, point[x].segment_tree_pos, 1)); x = point[point[x].up_chain_point].father; } if (point[x].deep > point[y].deep) swap (x, y); if (x != y) Answer = max (Answer, Segment_Tree.Query_Section (point[x].segment_tree_pos + 1, point[y].segment_tree_pos, 1)); return Answer; } void Change_chain (int x, int y) { while (point[x].up_chain_point != point[y].up_chain_point) { if (point[point[x].up_chain_point].deep < point[point[y].up_chain_point].deep) swap (x, y); Segment_Tree.Change_Section (point[point[x].up_chain_point].segment_tree_pos, point[x].segment_tree_pos, 1); x = point[point[x].up_chain_point].father; } if (point[x].deep > point[y].deep) swap (x, y); if (x != y) Segment_Tree.Change_Section (point[x].segment_tree_pos + 1, point[y].segment_tree_pos, 1); } void Change_Single (int x, int number) { x = (x << 1) - 1; int pos = point[edge[x].to].deep > point[edge[x].from].deep ? point[edge[x].to].segment_tree_pos : point[edge[x].from].segment_tree_pos; Segment_Tree.Change_Single (pos, 1, number); return ; } }; Tree_Chain_Type Make; int main (int argc, char *argv[]) { freopen ("maintaintree.in", "r", stdin); freopen ("maintaintree.out", "w", stdout); int N; read (N); int x, y, z; for (int i = 1; i < N; i++) { read (x); read (y); read (z); Make.Add_Edge (x, y, z); } Make.Dfs_1 (1, 0); Make.Dfs_2 (1, 1); Segment_Tree.Build (1, N, 1); char type[10]; while (scanf ("%s", type) && type[0] != 'D') { read (x); read (y); if (type[0] == 'Q') printf ("%d ", Make.Query_chain (x, y)); else if (type[0] == 'C') Make.Change_Single (x, y); else Make.Change_chain (x, y); } return 0; }