洛谷 P4556 [Vani 有约会] 雨天的尾巴 /【模板】线段树合并
# 主要思想:
顾名思义,线段是合并就是将多棵线段树合并到一起,要求线段树维护的数据可以支持合并,例如最大值,区间和等。
我们在进行合并时要把两棵线段树上相同的结构点合并到一起,换句话说,就是两棵线段树当前要合并的点所表示的区间是一样的。
例如,区间长度是 ,那么我们合并时要把 和 合并到一起 和 合并到一起。
好了,我们知道了主要思想后下面来看如何实现。
# 题解:
对于洛谷 P4556 这道题来说,我们要对这 个房屋每个点都建一棵权值线段树。
何为权值线段树:就是以题目中救济粮 为下角标建线段树,维护每种救济粮个数以及最多的是哪种.
记录种类为 的救济粮有多少。
记录第 个房屋中数量最多的救济粮种类是多少。
对于每次发放救济粮,暴力更新 到 的链是不现实的,这时我们就要用到树上差分的思想。
令 且 ,这样对于一个点来说,它的被覆盖次数(救济粮个数)就是以它为根的子树权值和。
思考一下为什么,可以手玩一下,随便挑几个点试试(emm 应该挺好理解的吧,这里不再赘述了)
下面再来谈谈动态开点线段树,我们不需要把整棵树都建出来,需要用哪个点就建哪个点。
直接令新节点等于 。
这样一来对于节点 ,它的左子树就不再是 ,右子树也不再是 ,所以我们要存 和
# 完整代码:
#include <iostream> | |
#include <cstdio> | |
#define log 20 | |
using namespace std; | |
const int N = 1e5 + 10; | |
const int M = 80 * N; | |
const int maxR = 1e5; | |
struct node{ | |
int v, nxt; | |
}edge[N << 1]; | |
int head[N], tot; | |
int n, m, cnt; | |
int f[N][21], dep[N]; | |
int sum[M], maxz[M], ls[M], rs[M]; | |
int ans[N], root[N]; | |
inline int read(){ | |
int x = 0, f = 1; | |
char ch = getchar(); | |
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();} | |
while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); | |
return f * x; | |
} | |
inline void add(int x, int y){ | |
edge[++tot] = (node){y, head[x]}; | |
head[x] = tot; | |
} | |
//---------------------------------------- 查找 lca 部分 | |
//dfs 预处理 | |
void dfs(int x, int fa){ | |
f[x][0] = fa; | |
dep[x] = dep[fa] + 1; | |
for(int i = 1; i < log; i++) | |
f[x][i] = f[f[x][i - 1]][i - 1]; | |
for(int i = head[x]; i; i = edge[i].nxt){ | |
int y = edge[i].v; | |
if(y == fa) continue; | |
dfs(y, x); | |
} | |
} | |
//lca 模板 | |
int lca(int a, int b){ | |
if(dep[a] < dep[b]) swap(a, b); | |
for(int i = log - 1; i >= 0; i--) | |
if(dep[f[a][i]] >= dep[b]) | |
a = f[a][i]; | |
if(a == b) return a; | |
for(int i = log - 1; i >= 0; i--) | |
if(f[a][i] != f[b][i]){ | |
a = f[a][i]; | |
b = f[b][i]; | |
} | |
return f[a][0]; | |
} | |
void pushup(int rt){ | |
if(sum[ls[rt]] >= sum[rs[rt]]) | |
sum[rt] = sum[ls[rt]], maxz[rt] = maxz[ls[rt]]; | |
else sum[rt] = sum[rs[rt]], maxz[rt] = maxz[rs[rt]]; | |
} | |
//---------------------------------------- 动态开点 或 更新权值线段树 | |
void update(int &rt, int l, int r, int z, int val){ | |
if(!rt) rt = ++cnt; // 动态开点 | |
if(l == r){ | |
sum[rt] += val; | |
maxz[rt] = z; | |
return; | |
} | |
int mid = (l + r) >> 1; | |
if(z <= mid) update(ls[rt], l, mid, z, val); | |
else update(rs[rt], mid + 1, r, z, val); | |
pushup(rt); | |
} | |
//---------------------------------------- 线段树合并 | |
int merge(int u, int v, int l, int r){ | |
if(!u || !v) return u + v; // 这里相当于一棵树为空的话,返回另一棵树,取个巧 | |
if(l == r){ | |
sum[u] += sum[v]; | |
return u; | |
} | |
int mid = (l + r) >> 1; | |
ls[u] = merge(ls[u], ls[v], l, mid); | |
rs[u] = merge(rs[u], rs[v], mid + 1, r); | |
pushup(u); | |
return u; | |
} | |
//---------------------------------------- 计算答案 | |
void calc(int x, int fa){ | |
for(int i = head[x]; i; i = edge[i].nxt){ | |
int y = edge[i].v; | |
if(y == fa) continue; | |
calc(y, x); | |
root[x] = merge(root[x], root[y], 1, maxR); // 整棵树从下到上合并 | |
} | |
ans[x] = maxz[root[x]]; | |
if(!sum[root[x]]) ans[x] = 0; | |
} | |
int main(){ | |
n = read(), m = read(); | |
for(int i = 1; i < n; i++){ | |
int u, v; | |
u = read(), v = read(); | |
add(u, v), add(v, u); | |
} | |
dfs(1, 0); | |
while(m--){ | |
int x, y, z; | |
x = read(), y = read(), z = read(); | |
int k = lca(x, y); | |
update(root[x], 1, maxR, z, 1); // 树上差分 | |
update(root[y], 1, maxR, z, 1); | |
update(root[k], 1, maxR, z, -1); | |
update(root[f[k][0]], 1, maxR, z, -1); | |
} | |
calc(1, 0); | |
for(int i = 1; i <= n; i++) | |
printf("%d\n", ans[i]); | |
return 0; | |
} |