Time Limit: 5000MS Memory Limit: 131072K
You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:
CHANGE i v Change the weight of the ith edge to v NEGATE a b Negate the weight of every edge on the path from a to b QUERY a b Find the maximum weight of edges on the path from a to b
The input contains multiple test cases. The first line of input contains an integer t (t ≤ 20), the number of test cases. Then follow the test cases.
Each test case is preceded by an empty line. The first nonempty line of its contains N (N ≤ 10,000). The next N − 1 lines each contains three integers a, b and c, describing an edge connecting nodes a and b with weight c. The edges are numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word “DONE” ends the test case.
For each “QUERY” instruction, output the result on a separate line.
1
3 1 2 1 2 3 2 QUERY 1 2 CHANGE 1 3 QUERY 1 2 DONE
1 3
有一个n个节点的树，然后根据题目所给出的查询条件，去查询最大权值，取反，更改边对应的区间中点的权值。
看到更改边来改变点的权值就可以想到是树链剖分，然后用线段树去维护，但是再维护的时候取反中，最大值要和最小值互换，因为变成了负数了，然后线段树的lazy标记为什么要判断lazy & 1而不是lazy是否存在，因为取反两次之后相当于不用取反。
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn = 10010; const int inf = 0x7fffffff; struct Edge { int to; int next; }; Edge edge[maxn << 1]; int num[maxn]; int top[maxn]; int deep[maxn]; int fa[maxn]; int p[maxn]; int fp[maxn]; int head[maxn]; int son[maxn]; int tot, pos; void init() { tot = 0; pos = 0; memset(head, -1, sizeof(head)); memset(son, -1, sizeof(son)); } void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; } void dfs(int u, int pre, int d) { deep[u] = d; fa[u] = pre; num[u] = 1; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v != pre) { dfs(v, u, d + 1); num[u] += num[v]; if (son[u] == -1 || num[son[u]] < num[v]) { son[u] = v; } } } } void getpos(int u, int sp) { top[u] = sp; p[u] = ++pos; fp[p[u]] = u; if (son[u] == -1) return ; getpos(son[u], sp); for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v != fa[u] && v != son[u]) { getpos(v, v); } } } struct NODE { int l; int r; int Max; int Min; int lazy; int mid () { return (l + r) >> 1; } }; NODE node[maxn << 2]; void pushup(int rt) { node[rt].Max = max(node[rt << 1].Max, node[rt << 1 | 1].Max); node[rt].Min = min(node[rt << 1].Min, node[rt << 1 | 1].Min); } void pushdown(int rt) { if (node[rt].lazy & 1) { node[rt << 1].lazy += node[rt].lazy; node[rt << 1 | 1].lazy += node[rt].lazy; node[rt << 1].Max = -node[rt << 1].Max; node[rt << 1].Min = -node[rt << 1].Min; swap(node[rt << 1].Max, node[rt << 1].Min); node[rt << 1 | 1].Max = -node[rt << 1 | 1].Max; node[rt << 1 | 1].Min = -node[rt << 1 | 1].Min; swap(node[rt << 1 | 1].Max, node[rt << 1 | 1].Min); node[rt].lazy = 0; } } void build(int l, int r, int rt) { node[rt].l = l; node[rt].r = r; node[rt].Min = inf; node[rt].Max = -inf; node[rt].lazy = 0; if (l == r) return ; int mid = node[rt].mid(); build(l, mid, rt << 1); build(mid + 1, r, rt << 1 | 1); pushup(rt); } void updata(int l, int r, int rt) { if (node[rt].l == l && node[rt].r == r) { node[rt].Max = -node[rt].Max; node[rt].Min = -node[rt].Min; swap(node[rt].Max, node[rt].Min); node[rt].lazy++; return ; } pushdown(rt); int mid = node[rt].mid(); if (r <= mid) updata(l, r, rt << 1); else if (l > mid) updata(l, r, rt << 1 | 1); else { updata(l, mid, rt << 1); updata(mid + 1, r, rt << 1 | 1); } pushup(rt); } void reupdata(int u, int v) { int f1 = top[u], f2 = top[v]; while (f1 != f2) { if (deep[f1] < deep[f2]) { swap(u, v); swap(f1, f2); } updata(p[f1], p[u], 1); u = fa[f1]; f1 = top[u]; } if (v == u) return ; if (deep[u] > deep[v]) swap(u, v); updata(p[son[u]], p[v], 1); } int query(int l, int r, int rt) { if (node[rt].l == l && node[rt].r == r) { return node[rt].Max; } pushdown(rt); int mid = node[rt].mid(); int res = -inf; if (r <= mid) res = max(res, query(l, r, rt << 1)); else if (l > mid) res = max(res, query(l, r, rt << 1 | 1)); else { res = max(res, query(l, mid, rt << 1)); res = max(res, query(mid + 1, r, rt << 1 | 1)); } pushup(rt); return res; } void updataedge(int k, int val, int rt) { if (node[rt].l == k && node[rt].r == k) { node[rt].Max = node[rt].Min = val; return ; } pushdown(rt); int mid = node[rt].mid(); if (k <= mid) updataedge(k, val, rt << 1); else updataedge(k, val, rt << 1 | 1); pushup(rt); } int findn(int u, int v) { int f1 = top[u], f2 = top[v], tmp = -inf; while (f1 != f2) { if (deep[f1] < deep[f2]) { swap(f1, f2); swap(u, v); } tmp = max(tmp, query(p[f1], p[u], 1)); u = fa[f1]; f1 = top[u]; } if (v == u) return tmp; if (deep[u] > deep[v]) swap(u, v); tmp = max(tmp, query(p[son[u]], p[v], 1)); return tmp; } int e[maxn][3]; int main() { int t, u, v, val, n; scanf("%d", &t); while (t--) { init(); scanf("%d", &n); for (int i = 1; i <= n - 1; i++) { scanf("%d %d %d", &e[i][0], &e[i][1], &e[i][2]); addedge(e[i][0], e[i][1]); addedge(e[i][1], e[i][0]); } dfs(1, 0, 1); getpos(1, 1); build(1, pos, 1); for (int i = 1; i <= n - 1; i++) { if (deep[e[i][0]] > deep[e[i][1]]) swap(e[i][0], e[i][1]); updataedge(p[e[i][1]], e[i][2], 1); } char s[10]; int a, b; while (scanf("%s", s) != EOF && s[0] != 'D') { scanf("%d %d", &a, &b); if (s[0] == 'Q') printf("%d\n", findn(a, b)); else if (s[0] == 'C') updataedge(p[e[a][1]], b, 1); else reupdata(a, b); } } return 0; } /* 1 15 7 1 93 6 2 41 6 1 48 14 4 62 12 15 43 7 8 2 2 10 80 7 13 92 13 5 91 13 11 5 15 1 79 2 3 21 9 12 7 15 4 33 Q 13 7 C 6 6 N 13 1 Q 3 15 C 12 11 N 14 11 Q 2 11 N 2 7 Q 6 7 C 11 10 N 3 8 Q 14 8 C 3 4 Q 8 13 C 5 1 N 7 1 Q 1 11 C 11 8 DONE */ /* 92 79 93 -48 93 92 92 */