[BZOJ3307][雨天的尾巴][树链剖分+线段树]

题目大意：

N<=100000 个点，形成一个树状结构。有 M<=100000 次发放，每次选择两个点 x,y ，对于 x 到y的路径上（含x,y)每个点发一袋 Z 类型的物品。完成所有发放后，询问每个点存放最多的是哪种物品。

思路：

考虑如果不是一棵树而是一段序列应该怎么做，显然我们可以开一棵权值线段树，对于一个命令(l,r,z)，把它拆分成 (l,z,+1) 和 (r+1,z,−1) 。也就是经过 l 时，在线段树的z位置上 +1 ，经过 r+1 时，在线段树的 z 位置上−1。这样可以保证这个命令的贡献只处于 [l,r] 的区间内。这样只要枚举每个点，把坐标位于该点的拆分命令都做一遍，然后在此时统计线段树上最大值所在的位置就好了。

如果是一棵树的话，把树树剖成很多条链后，在每条链上按序列上一样做就好了。

代码：

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; 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; for (; !(c >= '0' && c <= '9'); c = get()); for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get()); } inline void write(int x) { if (!x) return (void)puts("0"); static short s[12], t; while (x) s[++t] = x % 10, x /= 10; while (t) putchar('0' + s[t--]); putchar('\n'); } }; const int Maxn = 100010; int head[Maxn], sub; struct Edge { int to, nxt, v; Edge(void) {} Edge(const int &to, const int &nxt, const int &v) : to(to), nxt(nxt), v(v) {} } edge[2500005]; inline void add(const int &a, const int &b, const int &v = 0) { edge[++sub] = Edge(b, head[a], v), head[a] = sub; } int n, m, fa[Maxn], dep[Maxn], belong[Maxn], pos[Maxn], id[Maxn], siz[Maxn], dfn; inline void dfs1(int u) { siz[u] = 1; for (int i = head[u], v; i; i = edge[i].nxt) {; if ((v = edge[i].to) == fa[u]) continue; dep[v] = dep[u] + 1, fa[v] = u; dfs1(v); siz[u] += siz[v]; } } inline void dfs2(int u, int path) { pos[u] = ++dfn, id[dfn] = u, belong[u] = path; int k = 0; for (int i = head[u], v; i; i = edge[i].nxt) { v = edge[i].to; if (dep[v] > dep[u] && siz[v] > siz[k]) k = v; } if (!k) return; dfs2(k, path); for (int i = head[u], v; i; i = edge[i].nxt) { v = edge[i].to; if (dep[v] > dep[u] && v != k) dfs2(v, v); } } int Mx[Maxn << 2], Mxp[Maxn << 2], dis[Maxn], con[Maxn], tot, ans[Maxn]; inline bool cmp(int a, int b) { return (Mx[a] > Mx[b]) || (Mx[a] == Mx[b] && con[Mxp[a]] < con[Mxp[b]]); } inline void pushUp(int o) { if (cmp(o << 1, o << 1 | 1)) Mx[o] = Mx[o << 1], Mxp[o] = Mxp[o << 1]; else Mx[o] = Mx[o << 1 | 1], Mxp[o] = Mxp[o << 1 | 1]; } inline void build(int o, int l, int r) { if (l == r) return (void) (Mxp[o] = l); int mid = (l + r) >> 1; build(o << 1, l, mid), build(o << 1 | 1, mid + 1, r); pushUp(o); } inline void cover(int o, int l, int r, int pos, int val) { if (l == r) return (void)(Mx[o] += val); int mid = (l + r) >> 1; if (mid >= pos) cover(o << 1, l, mid, pos, val); else cover(o << 1 | 1, mid + 1, r, pos, val); pushUp(o); } int main(void) { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); IO::read(n), IO::read(m); for (int i = 1, a, b; i < n; i++) { IO::read(a), IO::read(b); add(a, b), add(b, a); } dfs1(1), dfs2(1, 1); sub = 0; memset(head, 0, sizeof head); for (int i = 1, x, y, z; i <= m; i++) { IO::read(x), IO::read(y), IO::read(z); if (!dis[z]) dis[z] = ++tot, con[tot] = z; z = dis[z]; while (belong[x] != belong[y]) { if (dep[belong[x]] < dep[belong[y]]) swap(x, y); add(pos[belong[x]], z, 1); add(pos[x] + 1, z, -1); x = fa[belong[x]]; } if (dep[x] > dep[y]) swap(x, y); add(pos[x], z, 1); add(pos[y] + 1, z, -1); } build(1, 1, m); for (int i = 1; i <= n; i++) { for (int j = head[i]; j; j = edge[j].nxt) cover(1, 1, m, edge[j].to, edge[j].v); ans[id[i]] = Mx[1] ? Mxp[1] : 0; } for (int i = 1; i <= n; i++) IO::write(con[ans[i]]); return 0; }

完。

By g1n0st