bzoj 3307 雨天的尾巴
内容
Description
N个点，形成一个树状结构。有M次发放，每次选择两个点x,y
对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成
所有发放后，每个点存放最多的是哪种物品。
Input
第一行数字N，M
接下来N-1行，每行两个数字a,b,表示a与b间有一条边
再接下来M行，每行三个数字x,y,z.如题
Output
输出有N行
每i行的数字表示第i个点存放最多的物品是哪一种，如果有
多种物品的数量一样，输出编号最小的。如果某个点没有物品
则输出0
Sample Input
20 50
8 6
10 6
18 6
20 10
7 20
2 18
19 8
1 6
14 20
16 10
13 19
3 14
17 18
11 19
4 11
15 14
5 18
9 10
12 15
11 14 87
12 1 87
14 3 84
17 2 36
6 5 93
17 6 87
10 14 93
5 16 78
6 15 93
15 5 16
11 8 50
17 19 50
5 4 87
15 20 78
1 17 50
20 13 87
7 15 22
16 11 94
19 8 87
18 3 93
13 13 87
2 1 87
2 6 22
5 20 84
10 12 93
18 12 87
16 10 93
8 17 93
14 7 36
7 4 22
5 9 87
13 10 16
20 11 50
9 16 84
10 17 16
19 6 87
12 2 36
20 9 94
9 2 84
14 1 94
5 5 94
8 17 16
12 8 36
20 17 78
12 18 50
16 8 94
2 19 36
10 18 36
14 19 50
4 12 50
Sample Output
87
36
84
22
87
87
22
50
84
87
50
36
87
93
36
94
16
87
50
50
1<=N,M<=100000
1<=a,b,x,y<=N
1<=z<=10^9
题解
对于每个点都维护一棵权值线段树，然后将标记差分，最后将每个节点的线段树与父亲节点的线段树合并即可。
#include <cstdio>
#include <algorithm>
#define mid (l + r >> 1)
#define lson t[rt].l, l, mid
#define rson t[rt].r, mid + 1, r
using namespace std;
const int N = 100010;
struct edge {
int to,next;
}e[N << 1];
int st[N], siz[N], top[N], son[N], fa[N], deep[N], p[N];
int tot, n, m, x, y, root[N];
void add(int x, int y) {
e[++tot].next = st[x];
e[tot].to = y, st[x] = tot;
}
void dfs1(int now) {
siz[now] = 1, p[++p[0]] = now;
for (int i = st[now]; i; i = e[i].next)
if (e[i].to != fa[now]) {
fa[e[i].to] = now, deep[e[i].to] = deep[now] + 1;
dfs1(e[i].to), siz[now] += siz[e[i].to];
if (siz[son[now]] < siz[e[i].to])
son[now] = e[i].to;
}
}
void dfs2(int now, int tp) {
top[now] = tp;
if (son[now]) dfs2(son[now], tp);
for (int i = st[now]; i; i = e[i].next)
if (e[i].to != fa[now] && e[i].to != son[now])
dfs2(e[i].to, e[i].to);
}
int lca(int x, int y) {
while (top[x] != top[y]) deep[top[x]] > deep[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
return deep[x] > deep[y] ? y : x;
}
struct datas {
int x, y, z;
}q[N];
bool comp(datas a, datas b) {
return a.z < b.z;
}
struct segt {
int l, r, typ, val;
}t[N * 50];
int sz, ref[N];
void update(int rt) {
t[rt].val = max(t[t[rt].l].val, t[t[rt].r].val);
t[rt].typ = (t[t[rt].l].val >= t[t[rt].r].val) ? t[t[rt].l].typ : t[t[rt].r].typ;
}
void inserts(int &rt, int l, int r, int pos, int v) {
if (!rt) rt = ++sz;
if (l == r) { t[rt].val += v, t[rt].typ = ref[l]; return; }
if (pos <= mid) inserts(lson, pos, v);
else inserts(rson, pos, v);
update(rt);
}
void merges(int &x, int y, int l, int r) {
if (!y) return;
if (!x) { x = y; return; }
if (l == r) { t[x].val += t[y].val; return; }
merges(t[x].l, t[y].l, l, mid);
merges(t[x].r, t[y].r, mid + 1, r);
update(x);
}
main() {
scanf("%d%d", &n, &m);
for (int i = 1; i < n; ++i)
scanf("%d%d", &x, &y),
add(x, y), add(y, x);
for (int i = 1; i <= n; ++i) root[i] = ++sz;
deep[1] = 1, dfs1(1), dfs2(1, 1);
for (int i = 1; i <= m; ++i)
scanf("%d%d%d", &q[i].x, &q[i].y, &q[i].z);
sort(q + 1, q + 1 + m, comp);
for (int i = 1, d = 0; i <= m; ++i) {
int a = q[i].x, b = q[i].y, c = lca(a, b);
if (q[i].z > q[i - 1].z) ref[++d] = q[i].z;
inserts(root[a], 0, m, d, 1), inserts(root[b], 0, m, d, 1), inserts(root[c], 0, m, d, -1);
if (c != 1) inserts(root[fa[c]], 0, m, d, -1);
}
for (int i = n; i > 1; --i) merges(root[fa[p[i]]], root[p[i]], 0, m);
for (int i = 1; i <= n; ++i) printf("%d\n", t[root[i]].typ);
}