在洛谷中查看
前言
将边权转化到点权的树剖，很好理解，但我就说说线段树部分。
原本想做 P1505 [国家集训队] 旅游 的，但是发现它需要边权转化点权，所以先做了这题，于是代码里维护了 \(minn\)、\(maxn\)、\(sum\)。
包含内容：线段树部分怎么写、本题随机数据生成器
线段树怎么写
先试着自己写一写
我们肯定要有两个标记：
- cover 覆盖标记
- add 加标记
但这两个标记会互相影响的，怎么办呢？
很显然，我们打上覆盖标记时，之前的加标记肯定已经没了（加在覆盖之前，所以清零），所以
void update_cover(int x, int l, int r, int w) {
if (l <= tree[x].l && tree[x].r <= r) {
tree[x].sum = siz(x) * w;
tree[x].minn = tree[x].maxn = w;
tree[x].cover = w;
tree[x].add = 0;//直接清空
return;
}
pushdown(x);
if (l <= tree[lson].r)update_cover(lson, l, r, w);
if (r >= tree[rson].l)update_cover(rson, l, r, w);
pushup(x);
}
\(\,\)
那怎么下传标记呢？
因为题目保证了每条树枝上果子的数量都是正数，所以我们设置覆盖标记初始值为 \(-1\)。
然后加操作直接加就行。
还有一个重要的地方：覆盖操作优先级大于加操作，因为打上覆盖标记时，将加标记清零了，所以如果加操作不为 \(0\) 的话，那它一定是在覆盖操作后进行的。
结合代码非常好理解：
void pushdown(int x) {
//先进行覆盖操作，因为当打上覆盖操作标记时，加标记已经清零了
if (tree[x].cover != -1) {
tree[lson].sum = siz(lson) * tree[x].cover;//修改左子树和
tree[rson].sum = siz(rson) * tree[x].cover;//修改右子树和
tree[lson].minn = tree[lson].maxn = tree[rson].minn = tree[rson].maxn = tree[x].cover;//修改左右子树最大最小值
tree[lson].cover = tree[rson].cover = tree[x].cover;//下传覆盖标记
tree[lson].add = tree[rson].add = 0;//清除加标记，不会误清理，因为如果覆盖后加操作的话，之前是已经下传过了
tree[x].cover = -1;//清除覆盖标记
}
if (tree[x].add) {
tree[lson].sum += siz(lson) * tree[x].add;//修改左子树和
tree[rson].sum += siz(rson) * tree[x].add;//修改右子树和
tree[lson].minn += tree[x].add;//修改左子树最小值
tree[lson].maxn += tree[x].add;//修改左子树最大值
tree[rson].minn += tree[x].add;//修改右子树最小值
tree[rson].maxn += tree[x].add;//修改右子树最大值
tree[lson].add += tree[x].add;
tree[rson].add += tree[x].add;//下传加标记
tree[x].add = 0;//清除加标记
}
}
你可能会有一点疑惑：为什么这样就是对的?
其实，线段树懒标记的下传是否正确，那就是有没有考虑到每种懒标记互相影响的情况，那这东西也是要练的（应该吧），所以只要我都考虑到了，那我就是对的。
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<#x<<" = "<<x<<endl;
const int N = 1e5 + 5;
int n, m, go[N], dep[N], siz[N], son[N], top[N], dfn[N], num, tmp[N], w[N];
string opt;
struct edge {
int to, w;
};
vector<edge> g[N];
struct Tmp_edge {
int u, v;
}tmp_edge[N];
struct segment_tree {
int l, r, minn, maxn;
ll sum, cover, add;
#define lson (x<<1)
#define rson (x<<1|1)
#define siz(x) (ll)(tree[x].r - tree[x].l + 1)
}tree[N << 2];
void pushup(int x) {
tree[x].sum = tree[lson].sum + tree[rson].sum;
tree[x].minn = min(tree[lson].minn, tree[rson].minn);
tree[x].maxn = max(tree[lson].maxn, tree[rson].maxn);
}
void build(int x, int l, int r) {
tree[x].l = l;
tree[x].r = r;
tree[x].minn = 0x3f3f3f3f;
tree[x].maxn = -0x3f3f3f3f;
tree[x].cover = -1;//不可能是负数，所以赋个负数
if (l == r) {
tree[x].minn = tree[x].maxn = tree[x].sum = w[l];
return;
}
int mid = l + r >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(x);
}
void pushdown(int x) {
//先进行覆盖操作，因为当打上覆盖操作标记时，加标记已经清零了
if (tree[x].cover != -1) {
tree[lson].sum = siz(lson) * tree[x].cover;//修改左子树和
tree[rson].sum = siz(rson) * tree[x].cover;//修改右子树和
tree[lson].minn = tree[lson].maxn = tree[rson].minn = tree[rson].maxn = tree[x].cover;//修改左右子树最大最小值
tree[lson].cover = tree[rson].cover = tree[x].cover;//下传覆盖标记
tree[lson].add = tree[rson].add = 0;//清除加标记，不会误清理，因为如果覆盖后加操作的话，之前是已经下传过了
tree[x].cover = -1;//清除覆盖标记
}
if (tree[x].add) {
tree[lson].sum += siz(lson) * tree[x].add;//修改左子树和
tree[rson].sum += siz(rson) * tree[x].add;//修改右子树和
tree[lson].minn += tree[x].add;//修改左子树最小值
tree[lson].maxn += tree[x].add;//修改左子树最大值
tree[rson].minn += tree[x].add;//修改右子树最小值
tree[rson].maxn += tree[x].add;//修改右子树最大值
tree[lson].add += tree[x].add;
tree[rson].add += tree[x].add;//下传加标记
tree[x].add = 0;//清除加标记
}
}
void update_cover(int x, int l, int r, int w) {
if (l <= tree[x].l && tree[x].r <= r) {
tree[x].sum = siz(x) * w;
tree[x].minn = tree[x].maxn = w;
tree[x].cover = w;
tree[x].add = 0;//直接清空
return;
}
pushdown(x);
if (l <= tree[lson].r)update_cover(lson, l, r, w);
if (r >= tree[rson].l)update_cover(rson, l, r, w);
pushup(x);
}
void update_add(int x, int l, int r, int w) {
if (l <= tree[x].l && tree[x].r <= r) {
tree[x].sum += siz(x) * w;
tree[x].minn += w;
tree[x].maxn += w;
tree[x].add += w;
return;
}
pushdown(x);
if (l <= tree[lson].r)update_add(lson, l, r, w);
if (r >= tree[rson].l)update_add(rson, l, r, w);
pushup(x);
}
int query_max(int x, int l, int r) {
if (l <= tree[x].l && tree[x].r <= r) return tree[x].maxn;
pushdown(x);
int max_ans = -0x3f3f3f3f;
if (l <= tree[lson].r)max_ans = max(max_ans, query_max(lson, l, r));
if (r >= tree[rson].l)max_ans = max(max_ans, query_max(rson, l, r));
return max_ans;
}
inline int read() {
int s = 0, f = 1; char c = getchar();
while (c < '0' || c>'9') { if (c == '-')f = -1; c = getchar(); }
while (c >= '0' && c <= '9') { s = (s << 1) + (s << 3) + (c ^ 48); c = getchar(); }
return s * f;
}
void dfs1(int x, int fa) {
go[x] = fa;
dep[x] = dep[fa] + 1;
siz[x] = 1;
for (int i = 0; i < g[x].size(); i++) {
int t = g[x][i].to;
if (t == fa)continue;
dfs1(t, x);
tmp[t] = g[x][i].w;
siz[x] += siz[t];
if (siz[t] > siz[son[x]])son[x] = t;
}
}
void dfs2(int x, int t) {
dfn[x] = ++num;
w[num] = tmp[x];
top[x] = t;
if (!son[x])return;
dfs2(son[x], t);
for (int i = 0; i < g[x].size(); i++) {
int to = g[x][i].to;
if (to == go[x] || to == son[x])continue;
dfs2(to, to);
}
}
void update_cover_chain(int x, int y, int w) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]])swap(x, y);
update_cover(1, dfn[top[x]], dfn[x], w);
x = go[top[x]];
}
if (dep[x] > dep[y])swap(x, y);
update_cover(1, dfn[x] + 1, dfn[y], w);//边上树剖
}
void update_add_chain(int x, int y, int w) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]])swap(x, y);
update_add(1, dfn[top[x]], dfn[x], w);
x = go[top[x]];
}
if (dep[x] > dep[y])swap(x, y);
update_add(1, dfn[x] + 1, dfn[y], w);//边上树剖
}
int query_max_chain(int x, int y) {
int max_ans = -0x3f3f3f3f;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]])swap(x, y);
max_ans = max(max_ans, query_max(1, dfn[top[x]], dfn[x]));
x = go[top[x]];
}
if (dep[x] > dep[y])swap(x, y);
if (x != y)max_ans = max(max_ans, query_max(1, dfn[x] + 1, dfn[y]));
return max_ans;//边上树剖
}
int main() {
n = read();
for (int i = 1; i < n; i++) {
int u = read(), v = read(), w = read();
tmp_edge[i] = Tmp_edge{ u,v };
g[u].push_back(edge{ v,w });
g[v].push_back(edge{ u,w });
}
dfs1(1, 1);
dfs2(1, 1);
build(1, 1, n);
while (true) {
cin >> opt;
if (opt == "Stop") break;
if (opt == "Change") {
int k = read(), w = read();
update_cover_chain(tmp_edge[k].u, tmp_edge[k].v, w);
}
if (opt == "Cover") {
int u = read(), v = read(), w = read();
if (u == v)continue;
update_cover_chain(u, v, w);
}
if (opt == "Add") {
int u = read(), v = read(), w = read();
if (u == v)continue;
update_add_chain(u, v, w);
}
if (opt == "Max") {
int u = read(), v = read();
if (u == v)cout << 0 << endl;
else printf("%d\n", query_max_chain(u, v));
}
}
return 0;
}
赠送对拍的随机数生成器（很烂）：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
freopen("test.in","w",stdout);
srand(time(0));
int n = 100, m = 1000;
printf("%d\n",n);
for(int i=2;i<=n;i++)printf("%d %d %d\n",rand()%(i-1)+1,i,rand()%100);
while(m--){
int opt = rand()%4;
if(opt == 0)printf("%s %d %d\n","Max",rand()%n+1,rand()%n+1);
if(opt == 1)printf("%s %d %d %d\n","Add",rand()%n+1,rand()%n+1,rand()%100);
if(opt == 2)printf("%s %d %d %d\n","Cover",rand()%n+1,rand()%n+1,rand()%100);
if(opt == 3)printf("%s %d %d\n","Change",rand()%(n-1)+1,rand()%100);
}
printf("%s","Stop");
return 0;
}