[BZOJ4372][烁烁的游戏][动态树分治+线段树+LCA]

2019-11-06 06:32:05

字体：大中小

来源：转载

供稿：网友

[BZOJ4372][烁烁的游戏][动态树分治+线段树+LCA]

题目大意：

给定一颗n $n$ 个节点的树，边权均为1 $1$ ，初始每个点权值为0 $0$ 。其中操作Q $Q$ x $x$ 询问x点的点权，操作 M $M$ x $x$ d $d$ w $w$ 把x $x$ 点周围距离不超过w $w$ 的点权值加上w $w$ 。

思路：

应该是一棵蛮裸的动态树分治，和BZOJ3730 : http://blog.csdn.net/g1n0st/article/details/56674271类似吧。

也是在每个节点上开一棵动态权值线段树。只不过这道题是初始值为0 $0$ ，而且要求的是区间修改，单点询问。

坑：

WTF求重心的时候存每个节点最大的儿子的数组没有清空，到时求到的并不是重心。。。效率瞬间hhhh，还以为是常数问题优化了好久。

代码：

#include <bits/stdc++.h>using namespace std;const int Maxn = 200005;inline int Max(const int &a, const int &b) { return a > b ? a : b;}inline int Min(const int &a, const int &b) { return a < b ? a : b;}inline void swap(int &a, int &b) { static int c; c = a; a = b; b = c;}int n, k;int head[Maxn], sub;struct Edge { int to, nxt; Edge(void) {} Edge(const int &to, const int &nxt) : to(to), nxt(nxt) {}} edge[Maxn << 1];inline void add(int a, int b) { edge[++sub] = Edge(b, head[a]), head[a] = sub;}int siz[Maxn], son[Maxn], root, S, rt[Maxn][2], p[Maxn];bool vis[Maxn];namespace IO { inline char get(void) { static char buf[1000000], *p1 = buf, *p2 = buf; if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin); if (p1 == p2) return EOF; } return *p1++; } inline void read(int &x) { x = 0; static char c; bool f = 0; for (; !(c >= '0' && c <= '9'); c = get()) if (c == '-') f = 1; for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get()); if (f) x = -x; } inline void read(char &x) { x = get(); while (!(x >= 'A' && x <= 'Z')) x = get(); } inline void write(int x) { if (!x) return (void)puts("0"); if (x < 0) putchar('-'), x = -x; static short s[12], t; while (x) s[++t] = x % 10, x /= 10; while (t) putchar('0' + s[t--]); putchar('/n'); }};namespace Q {#define Maxw 20000500 int s[Maxw], ls[Maxw], rs[Maxw], sz; inline void insert(int &o, int l, int r, int L, int R, int v) { if (!o) o = ++sz; if (l >= L && r <= R) { s[o] += v; return; } int mid = (l + r) >> 1; if (mid >= L) insert(ls[o], l, mid, L, R, v); if (mid < R) insert(rs[o], mid + 1, r, L, R, v); } inline int query(int o, int l, int r, int v) { if (!o || l == r) return s[o]; int mid = (l + r) >> 1; if (mid >= v) return s[o] + query(ls[o], l, mid, v); else return s[o] + query(rs[o], mid + 1, r, v); }#undef Maxw};namespace LCA { int ff[Maxn][25], dep[Maxn]; inline void dfs1(int u, int fa) { ff[u][0] = fa; for (int i = 1; i <= 20; i++) { ff[u][i] = ff[ff[u][i - 1]][i - 1]; } for (int i = head[u], v; i; i = edge[i].nxt) { v = edge[i].to; if (v == fa) continue; dep[v] = dep[u] + 1; dfs1(v, u); } } inline int lca(int x, int y) { if (dep[x] < dep[y]) swap(x, y); int tmp = dep[x] - dep[y]; for (int k = 0, j = 1; j <= tmp; j <<= 1, k++) if (tmp & j) x = ff[x][k]; while (x != y) { int j = 0; while (ff[x][j] != ff[y][j]) j++; if (j) j--; x = ff[x][j], y = ff[y][j]; } return x; } inline int dist(int x, int y) { return dep[x] + dep[y] - (dep[lca(x, y)] << 1); }};inline void getroot(int u, int fa) { siz[u] = 1; son[u] = 0; for (int i = head[u], v; i; i = edge[i].nxt) { v = edge[i].to; if (v == fa || vis[v]) continue; getroot(v, u); siz[u] += siz[v]; son[u] = Max(son[u], siz[v]); } son[u] = Max(son[u], S - siz[u]); if (son[u] < son[root]) root = u;}inline void solve(int x) { vis[x] = 1; for (int i = head[x], v; i; i = edge[i].nxt) { v = edge[i].to; if (vis[v]) continue; S = siz[v]; root = 0; getroot(v, 0); p[root] = x; solve(root); }}inline void Modify(int x, int d, int w) { Q::insert(rt[x][0], 0, n, 0, d, w); int dist = 0; for (int i = x; p[i]; i = p[i]) { dist = LCA::dist(x, p[i]); if (dist > d) continue; Q::insert(rt[i][1], 0, n, 0, d - dist, w); Q::insert(rt[p[i]][0], 0, n, 0, d - dist, w); }}inline int Ask(int x) { int dist = 0, ret = 0; ret += Q::query(rt[x][0], 0, n, 0); for (int i = x; p[i]; i = p[i]) { dist = LCA::dist(x, p[i]); ret += Q::query(rt[p[i]][0], 0, n, dist); ret -= Q::query(rt[i][1], 0, n, dist); } return ret;}int main(void) { //freopen("4372.in", "r", stdin); //freopen("4372.out", "w", stdout); IO::read(n), IO::read(k); for (int i = 1; i < n; i++) { int a, b; IO::read(a), IO::read(b); add(a, b), add(b, a); } LCA::dfs1(1, 0); S = son[0] = n; getroot(1, 0); solve(root); char op; int x, d, w; while (k--) { if (IO::read(op), op == 'Q') { IO::read(x); IO::write(Ask(x)); } else { IO::read(x), IO::read(d), IO::read(w); Modify(x, d, w); } } return 0;}

完。

By g1n0st

上一篇：对称矩阵的压缩存储

下一篇：二叉树的四种遍历算法