HDU 5029 Relief grain
來源：程序員人生 發(fā)布時間：2014-10-08 08:00:00 閱讀次數(shù)：3261次
題意：
一棵樹 m次染色 每次染色一條路徑 顏色不會覆蓋會積累 問每個點覆蓋次數(shù)最多的顏色是什么
思路：
樹上路徑操作不是樹鏈剖分就是LCT 對于每次染色 相當(dāng)于讓那種顏色的權(quán)值+1
一般的熟練剖分都是將樹剖成線段然后放在線段樹上 這題只是剖成線段 然后對于路徑的染色 就變成了對多個線段的染色
由于剖分已經(jīng)使樹變成了線性的結(jié)構(gòu) 因此我們可以利用“頭加尾減”的方式維護(hù) 即 如果染色[u,v]那么u處++然后v+1處--
由于本題有多種顏色 為了快速解決區(qū)間更新和求最大值問題我們需要使用線段樹 即維護(hù)權(quán)值線段樹 然后從頭到尾掃一遍即可
代碼：
#pragma comment(linker,"/STACk:10240000,10240000")
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<cassert>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long LL;
#define N 100010
#define L(x) (x<<1)
#define R(x) ((x<<1)|1)
#define MI(x,y) ((x+y)>>1)
int n, m, tot, idx;
int head[N], pre[N], size[N], dep[N], hson[N], top[N], tid[N], ftid[N], ans[N];
struct Edge {
int u, v, next;
} ed[N * 2];
struct Add {
int c, v, next;
} ad[N * 40];
struct Tree {
int l, r, v;
} d[N * 4];
void addedge(int u, int v) {
ed[tot].u = u;
ed[tot].v = v;
ed[tot].next = head[u];
head[u] = tot++;
}
void add(int u, int c, int v) {
ad[tot].c = c;
ad[tot].v = v;
ad[tot].next = head[u];
head[u] = tot++;
}
void dfs1(int u, int fa) {
pre[u] = fa;
size[u] = 1;
dep[u] = dep[fa] + 1;
hson[u] = 0;
for (int i = head[u]; ~i; i = ed[i].next) {
int v = ed[i].v;
if (v != fa) {
dfs1(v, u);
if (size[v] > size[hson[u]])
hson[u] = v;
size[u] += size[v];
}
}
}
void dfs2(int u, int tp) {
tid[u] = idx;
ftid[idx] = u;
idx++;
top[u] = tp;
if (hson[u])
dfs2(hson[u], tp);
for (int i = head[u]; ~i; i = ed[i].next) {
int v = ed[i].v;
if (v != pre[u] && v != hson[u])
dfs2(v, v);
}
}
void Update(int u, int v, int c) {
int fu = top[u], fv = top[v];
while (fu != fv) {
if (dep[fu] >= dep[fv]) {
add(tid[fu], c, 1);
add(tid[u] + 1, c, -1);
u = pre[fu];
fu = top[u];
} else {
add(tid[fv], c, 1);
add(tid[v] + 1, c, -1);
v = pre[fv];
fv = top[v];
}
}
if (dep[u] > dep[v])
swap(u, v);
add(tid[u], c, 1);
add(tid[v] + 1, c, -1);
}
void build(int l, int r, int i) {
d[i].l = l;
d[i].r = r;
d[i].v = 0;
if (l == r)
return;
int mid = MI(l,r);
build(l, mid, L(i));
build(mid + 1, r, R(i));
}
void up(int i) {
d[i].v = max(d[L(i)].v, d[R(i)].v);
}
void update(int p, int i, int v) {
if (d[i].l == d[i].r) {
d[i].v += v;
return;
}
int mid = MI(d[i].l,d[i].r);
if (p <= mid)
update(p, L(i), v);
else
update(p, R(i), v);
up(i);
}
int query(int i) {
if (d[i].l == d[i].r)
return d[i].l;
if (d[i].v == d[L(i)].v)
return query(L(i));
else
return query(R(i));
}
int main() {
int i, u, v, c;
while (~scanf("%d%d", &n, &m)) {
if (!n && !m)
break;
tot = 0;
memset(head, -1, sizeof(head));
for (i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
dfs1(1, 0);
idx = 1;
dfs2(1, 1);
tot = 0;
memset(head, -1, sizeof(head));
for (i = 1; i <= m; i++) {
scanf("%d%d%d", &u, &v, &c);
Update(u, v, c);
}
build(0, 100001, 1);
for (u = 1; u <= n; u++) {
for (i = head[u]; ~i; i = ad[i].next)
update(ad[i].c, 1, ad[i].v);
ans[ftid[u]] = query(1);
}
for (i = 1; i <= n; i++) {
printf("%d
", ans[i]);
assert(ans[i] >= 0 && ans[i] <= 100000);
}
}
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進(jìn)行捐贈
