首页 > 代码库 > （树链剖分+线段树）POJ - 3237 Tree
（树链剖分+线段树）POJ - 3237 Tree
前言：
一直听说树链剖分-树链剖分，现在见识一下，，，感觉不是很难0.0
看了一下kuangbin模板基本秒懂
对于点，按重边优先给予每个点一个编号，对于一条重链上的点，编号则是连续的，将所有编号映射到线段树上，即可进行一切区间操作。
对于边的处理，我们将所有边对应到这条边节点更深的那个点上即可。
如果需要的操作只有求和，和单点更新/区间更新，直接用树状数组也是可以的，可能常数大那么一点点。
如果还需要更加强大的操作，显然用splay树维护也是可以的。。
比如树链上所有权值翻转等等。。不过，，这样差不多应该就快到LCT了。。虽然自己不会。。
不过过几天就该看了。
题意：
一棵树，每条边有一个权值，三种操作：
1、改变第i条边权值为v
2、将节点a到节点b之间的边权值取反
3、查询a到b之间最大的边权值
分析：
显然就是普通的树链剖分和线段树
但是要记得pushdown，
而对于lazy标记rev，当传下去的时候，不应该直接赋值为1或者0，而应该直接取反，用异或即可。
代码：
1 #include <math.h> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <string.h> 5 #include <time.h> 6 #include <algorithm> 7 #include <iostream> 8 #include <map> 9 #include <queue> 10 #include <set> 11 #include <string> 12 #include <vector> 13 using namespace std; 14 15 const int maxn = 100010; 16 const int inf = 0x3f3f3f3f; 17 18 struct Edge { 19 int to, next; 20 } edge[maxn << 1]; 21 22 int head[maxn], tot; 23 int top[maxn]; 24 int fa[maxn]; 25 int deep[maxn]; 26 int num[maxn]; 27 int p[maxn]; 28 int fp[maxn]; 29 int son[maxn]; 30 int pos; 31 32 void init() { 33 tot = 0; 34 memset(head, -1, sizeof head); 35 pos = 0; 36 memset(son, -1, sizeof son); 37 } 38 39 void addedge(int u, int v) { 40 edge[tot].to = v; 41 edge[tot].next = head[u]; 42 head[u] = tot++; 43 } 44 void dfs1(int u, int pre, int d) { 45 deep[u] = d; 46 fa[u] = pre; 47 num[u] = 1; 48 for (int i = head[u]; i != -1; i = edge[i].next) { 49 int v = edge[i].to; 50 if (v != pre) { 51 dfs1(v, u, d + 1); 52 num[u] += num[v]; 53 if (son[u] == -1 || num[v] > num[son[u]]) son[u] = v; 54 } 55 } 56 } 57 58 void getpos(int u, int sp) { 59 top[u] = sp; 60 p[u] = pos++; 61 fp[p[u]] = u; 62 if (son[u] == -1) return; 63 getpos(son[u], sp); 64 for (int i = head[u]; i != -1; i = edge[i].next) { 65 int v = edge[i].to; 66 if (v != son[u] && v != fa[u]) getpos(v, v); 67 } 68 } 69 70 struct Node { 71 int left, right, maxs, mins; 72 int rev; 73 } node[maxn << 2]; 74 75 void build(int n, int left, int right) { 76 node[n].left = left; 77 node[n].right = right; 78 node[n].maxs = 0; 79 node[n].mins = 0; 80 node[n].rev = 0; 81 if (left == right) return; 82 int mid = (left + right) >> 1; 83 build(n << 1, left, mid); 84 build(n << 1 | 1, mid + 1, right); 85 } 86 87 void push_up(int n) { 88 node[n].maxs = max(node[n << 1].maxs, node[n << 1 | 1].maxs); 89 node[n].mins = min(node[n << 1].mins, node[n << 1 | 1].mins); 90 } 91 92 void push_down(int n) { 93 if (node[n].left == node[n].right) return; 94 if (node[n].rev) { 95 node[n << 1].rev ^= 1; 96 node[n << 1 | 1].rev ^= 1; 97 swap(node[n << 1].mins, node[n << 1].maxs); 98 node[n << 1].mins *= -1; 99 node[n << 1].maxs *= -1;100 swap(node[n << 1 | 1].mins, node[n << 1 | 1].maxs);101 node[n << 1 | 1].mins *= -1;102 node[n << 1 | 1].maxs *= -1;103 node[n].rev = 0;104 }105 }106 107 void update(int n, int pos, int val) {108 if (node[n].left == node[n].right) {109 node[n].maxs = val;110 node[n].mins = val;111 node[n].rev = 0;112 return;113 }114 push_down(n);115 int mid = (node[n].left + node[n].right) >> 1;116 if (pos <= mid)117 update(n << 1, pos, val);118 else119 update(n << 1 | 1, pos, val);120 push_up(n);121 }122 123 void Rev(int n, int left, int right) {124 if (left <= node[n].left && node[n].right <= right) {125 node[n].rev ^= 1;126 swap(node[n].mins, node[n].maxs);127 node[n].mins *= -1;128 node[n].maxs *= -1;129 return;130 }131 push_down(n);132 int mid = (node[n].left + node[n].right) >> 1;133 if (mid >= left) Rev(n << 1, left, right);134 if (mid < right) Rev(n << 1 | 1, left, right);135 push_up(n);136 }137 138 int query(int n, int left, int right) {139 if (left <= node[n].left && node[n].right <= right) {140 return node[n].maxs;141 }142 push_down(n);143 int mid = (node[n].left + node[n].right) >> 1;144 int maxs = -inf;145 if (mid >= left) maxs = max(maxs, query(n << 1, left, right));146 if (mid < right) maxs = max(maxs, query(n << 1 | 1, left, right));147 push_up(n);148 return maxs;149 }150 151 int findMax(int u, int v) {152 int f1 = top[u], f2 = top[v];153 int tmp = -inf;154 while (f1 != f2) {155 if (deep[f1] < deep[f2]) {156 swap(f1, f2);157 swap(u, v);158 }159 tmp = max(tmp, query(1, p[f1], p[u]));160 u = fa[f1];161 f1 = top[u];162 }163 if (u == v) return tmp;164 if (deep[u] > deep[v]) swap(u, v);165 return max(tmp, query(1, p[son[u]], p[v]));166 }167 168 void Negate(int u, int v) {169 int f1 = top[u], f2 = top[v];170 while (f1 != f2) {171 if (deep[f1] < deep[f2]) {172 swap(f1, f2);173 swap(u, v);174 }175 Rev(1, p[f1], p[u]);176 u = fa[f1];177 f1 = top[u];178 }179 if (u == v) return;180 if (deep[u] > deep[v]) swap(u, v);181 Rev(1, p[son[u]], p[v]);182 }183 184 int e[maxn][3];185 186 int main() {187 // freopen("1.out", "w", stdout);188 int t;189 int n;190 scanf("%d", &t);191 while (t--) {192 init();193 scanf("%d", &n);194 for (int i = 0; i < n - 1; i++) {195 int u, v, c;196 scanf("%d%d%d", &e[i][0], &e[i][1], &e[i][2]);197 addedge(e[i][0], e[i][1]);198 addedge(e[i][1], e[i][0]);199 }200 dfs1(1, 0, 0);201 getpos(1, 1);202 build(1, 0, pos - 1);203 for (int i = 0; i < n - 1; i++) {204 if (deep[e[i][0]] > deep[e[i][1]]) swap(e[i][0], e[i][1]);205 update(1, p[e[i][1]], e[i][2]);206 }207 char op[10];208 int u, v;209 while (scanf("%s", op)) {210 if (op[0] == ‘D‘) break;211 scanf("%d%d", &u, &v);212 if (op[0] == ‘Q‘)213 printf("%d\n", findMax(u, v));214 else if (op[0] == ‘N‘) {215 Negate(u, v);216 } else {217 update(1, p[e[u - 1][1]], v);218 }219 }220 }221 return 0;222 }
（树链剖分+线段树）POJ - 3237 Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。