bzoj1036 [ZJOI2008]树的统计Count （树链剖分

Description一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身Input输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。接下来n行，每行一个整数，，第i行的整数wi表示节点i的权值。接下来1行，为一个整数q，表示操作的总数。接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。 对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。Output对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。Sample Input4 1 2 2 3 4 1 4 2 1 3 12 QMAX 3 4 QMAX 3 3 QMAX 3 2 QMAX 2 3 QSUM 3 4 QSUM 2 1 CHANGE 1 5 QMAX 3 4 CHANGE 3 6 QMAX 3 4 QMAX 2 4 QSUM 3 4Sample Output*4 1 2 2 10 6 5 6 5 16题解先说下树链剖分。

关于几个概念：

树链剖分就是把对树的操作分解为对几条重链的操作。 需要注意单独一个节点也算重链。 如下图：

树中所有的重链：

树链剖分需要借助的几个数组：

步骤：

此时问题简单多了，前面说过，树链剖分就是把对树的操作转化为对几条重链的操作，那么如何维护一条重链呢？ 很显然，因为一条重链上的mark值都是连续的，所以可以用线段树或splay维护。

再来说下本题

树链剖分的大概思路已经明白了，那么如何求两点之间的距离（最大值同理）呢？

先找出的距离为例： 求在一条重链上，所以线段树直接可以求）。。

至此本题解决。

;const int MAXN = 30005;int n, q;int value[MAXN];vector<int> edges[MAXN];int tot = 0;int dfsver[MAXN << 1], first[MAXN];int ST[MAXN << 1][20];int siz[MAXN], deep[MAXN], max_son[MAXN];int mark[MAXN], top[MAXN];int fa[MAXN];void dfs_size(int x, int pre, int dep) {dfsver[++tot] = x;first[x] = tot;deep[x] = dep;max_son[x] = 0;siz[x] = 1;for (int i = 0; i < edges[x].size(); i++) {int nex = edges[x][i];if (nex == pre) continue;dfs_size(nex, x, dep + 1);dfsver[++tot] = x;fa[nex] = x;siz[x] += siz[nex];if (!max_son[x] || siz[nex] > siz[max_son[x]])max_son[x] = nex;}}int _num = 0;void dfs_remark(int x, int pre, int topx) {top[x] = topx;mark[x] = ++_num;if (max_son[x]) dfs_remark(max_son[x], x, topx);for (int i = 0; i < edges[x].size(); i++) {int nex = edges[x][i];if (nex == pre) continue;if (max_son[x] != nex)dfs_remark(nex, x, nex);}}void RMQ() {for (int i = 1; i <= tot; i++)ST[i][0] = dfsver[i];for (int j = 1; (1 << j) <= tot; j++) {for (int i = 1; i + (1 << j) – 1 < tot; i++) {int a = ST[i][j – 1], b = ST[i + (1 << j – 1)][j – 1];ST[i][j] = deep[a] < deep[b] ? a : b;}}}int LCA(int a, int b) {int x = first[a], y = first[b];if (x > y) swap(x, y);int k = int(log(y – x + 1) / log(2));int l = ST[x][k], r = ST[y – (1 << k) + 1][k];int res = deep[l] < deep[r] ? l : r;return res;}int sum[MAXN << 2], mx[MAXN << 2];void push_up(int rt) { sum[rt] = sum[lch] + sum[rch]; mx[rt] = max(mx[lch], mx[rch]); }void build_tree(int l, int r, int rt) {int mid = l + r >> 1;sum[rt] = 0;mx[rt] = INT_MIN;if (l == r) return;build_tree(lson);build_tree(rson);}void insert(int l, int r, int rt, int id, int val) {if (l == r) {sum[rt] = mx[rt] = val;return;}int mid = l + r >> 1;if (id <= mid) insert(lson, id, val);else insert(rson, id, val);push_up(rt);}struct Node{int sum, mx;Node() {}Node(int a, int b) : sum(a), mx(b) {}};Node query(int l, int r, int rt, int L, int R) {if (L <= l && R >= r)return Node(sum[rt], mx[rt]);int mid = l + r >> 1;Node t;int sum = 0, mx = INT_MIN;if (L <= mid) {t = query(lson, L, R);sum += t.sum;mx = max(mx, t.mx);}if (mid < R) {t = query(rson, L, R);sum += t.sum;mx = max(mx, t.mx);};t = Node(sum, mx);return t;}int main() {scanf(“%d”, &n);int a, b;for (int i = 1; i < n; i++) {scanf(“%d %d”, &a, &b);edges[a].push_back(b);edges[b].push_back(a);}for (int i = 1; i <= n; i++)scanf(“%d”, &value[i]);scanf(“%d”, &q);dfs_size(1, 1, 1);RMQ();dfs_remark(1, 1, 1);build_tree(1, n, 1);for (int i = 1; i <= n; i++) insert(1, n, 1, mark[i], value[i]);char op[8];int x, y;for (int i = 0; i < q; i++) {scanf(“%s”, op);scanf(“%d %d”, &x, &y);if (op[0] == ‘C’) insert(1, n, 1, mark[x], y);else {int lca = LCA(x, y);int sum = 0;int mx = INT_MIN;while (x && deep[top[x]] >= deep[lca]) {Node t = query(1, n, 1, mark[top[x]], mark[x]);sum += t.sum;mx = max(mx, t.mx);x = fa[top[x]];}if (x && deep[x] >= deep[lca]) {Node t = query(1, n, 1, mark[lca], mark[x]);sum += t.sum;mx = max(mx, t.mx);}while (y && deep[top[y]] >= deep[lca]) {Node t = query(1, n, 1, mark[top[y]], mark[y]);sum += t.sum;mx = max(mx, t.mx);y = fa[top[y]];}if (y && deep[y] >= deep[lca]) {Node t = query(1, n, 1, mark[lca], mark[y]);sum += t.sum;mx = max(mx, t.mx);}sum -= query(1, n, 1, mark[lca], mark[lca]).sum;if (op[1] == ‘M’) printf(“%d\n”, mx);else printf(“%d\n”, sum);}}return 0;}然后再顺便说一下LCT人生好如足球赛,看自家总是无奈,对人家总是优待,