本文共 4403 字，大约阅读时间需要 14 分钟。
bestcoder round#45 1003 题，给定两个点，要我们求这两个点的树上路径所经过的点的权值是否出现过奇数次。
什么是树链剖分呢？ 就是把树的边分成轻链和重链
http://blog..com.cn/s/blog_6974c8b20100zc61.html
剖分后的树有如下性质：
第一次dfs进行树链剖分，求出了轻链和重链
那么要询问树上任意两点路径权值的最大值， 只要上depth大的那个点往上走， 如果往上走的时候，遇到的重链，那么可以进去区间查询，然后一次
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 using namespace std; 14 #pragma comment(linker, "/STACK:1024000000,1024000000") 15 #pragma warning(disable:4996) 16 typedef long long LL; 17 const int INF = 1<<30; 18 void input(int &x) 19 { 20 char ch = getchar(); 21 while (ch<'0' || ch>'9') 22 ch = getchar(); 23 x = 0; 24 while (ch >= '0'&&ch <= '9') 25 { 26 x = x * 10 + ch - '0'; 27 ch = getchar(); 28 } 29 } 30 /* 31 第一次dfs进行树链剖分，求出了轻链和重链 32 第二次dfs对树的结点进行了重新编号， 重链上的结点的编号是连续的 33 那么重链上的点在线段树中的区间是连续的 34 剖分后的树有如下性质： 35 性质1：如果(v,u)为轻边，则siz[u] * 2 < siz[v]； 36 性质2：从根到某一点的路径上轻链、重链的个数都不大于logn。 37 38 那么要询问树上任意两点路径权值的最大值， 只要上depth大的那个点往上走， 如果往上走的时候，遇到的重链，那么可以进去区间查询，然后一次 39 走过重链 40 根据性质2：每次询问的复杂度是O(logn*logn) 41 */ 42 const int N = 100000 + 10; 43 int size[N], depth[N], son[N], fa[N], w[N], top[N], ra[N], num; 44 int value[N]; 45 int tree[N * 4]; 46 vector g[N]; 47 int ans; 48 void dfs(int u) 49 { 50 size[u] = 1; 51 son[u] = 0; 52 for (int i = 0; i < g[u].size(); ++i) 53 { 54 int v = g[u][i]; 55 if (v != fa[u]) 56 { 57 depth[v] = depth[u] + 1; 58 fa[v] = u; 59 dfs(v); 60 size[u] += size[v]; 61 if (size[v]>size[son[u]]) 62 son[u] = v; 63 } 64 } 65 } 66 void dfs2(int u, int tp) 67 { 68 top[u] = tp; 69 w[u] = ++num;//对树上的结点进行编号 70 ra[num] = u; 71 //因为优先dfs重儿子，所以一条重链上的点的编号是连续的 72 if (son[u] != 0) 73 dfs2(son[u], top[u]); 74 for (int i = 0; i < g[u].size(); ++i) 75 { 76 int v = g[u][i]; 77 if (v != son[u] && v != fa[u]) 78 dfs2(v, v); 79 } 80 } 81 void pushUp(int rt) 82 { 83 tree[rt] = tree[rt << 1] ^ tree[rt << 1 | 1]; 84 } 85 void build(int l, int r, int rt) 86 { 87 if (l == r) 88 { 89 tree[rt] = value[ra[l]];//ra[l] 是编号为l的是哪个结点 90 return; 91 } 92 int mid = (l + r) >> 1; 93 build(l, mid, rt << 1); 94 build(mid + 1, r, rt << 1 | 1); 95 pushUp(rt); 96 } 97 //修改某个结点的值， 那么要将父区间异或旧的值（即去除原先的值），然后异或新的值 98 void update(int l, int r, int rt, int pos, int newVal, int oldVal) 99 {100 tree[rt] = tree[rt] ^ oldVal^newVal;101 if (l == r)102 return;103 int mid = (l + r) >> 1;104 if (pos <= mid)105 update(l, mid, rt << 1, pos, newVal, oldVal);106 else107 update(mid + 1, r, rt << 1 | 1, pos, newVal, oldVal);108 }109 void query(int l, int r, int rt, int L, int R)110 {111 if (L <= l && R >= r)112 {113 ans ^= tree[rt];114 return;115 }116 int mid = (l + r) >> 1;117 if (L <= mid)118 query(l, mid, rt << 1, L, R);119 if (R > mid)120 query(mid + 1, r, rt << 1 | 1, L, R);121 }122 int main()123 {124 int t, n, q, op,a, b;125 scanf("%d", &t);126 while (t--)127 {128 num = 0;129 scanf("%d%d", &n, &q);130 for (int i = 1; i <= n; ++i)131 g[i].clear();132 for (int i = 1; i < n; ++i)133 {134 scanf("%d%d", &a, &b);135 g[a].push_back(b);136 g[b].push_back(a);137 }138 for (int i = 1; i <= n; ++i)139 {140 //scanf("%d", &value[i]);141 input(value[i]);142 value[i]++;143 }144 depth[1] = fa[1] = 0;145 dfs(1);146 dfs2(1, 1);147 build(1, n, 1);148 while (q--)149 {150 scanf("%d%d%d", &op, &a, &b);151 152 if (op == 0)153 {154 b++;155 update(1, n, 1, w[a], b, value[a]);156 value[a] = b;157 }158 else159 {160 ans = 0;161 //不停的往上走，像lca一样，不过比lca更优，因为有重链的存在，可以一次走很多部162 while (top[a] != top[b])163 {164 if (depth[top[a]] < depth[top[b]])165 swap(a, b);166 query(1, n, 1, w[top[a]], w[a]);167 a = fa[top[a]];168 }169 if (depth[a] > depth[b])170 swap(a, b);171 query(1, n, 1, w[a], w[b]);172 if (ans == 0)173 printf("%d\n", -1);174 else175 printf("%d\n", ans - 1);176 }177 }178 }179 return 0;180 }
转载于:https://www.cnblogs.com/justPassBy/p/4623313.html
