已经查明是线段树的问题，按题解思路写线段树过了。但还是没有搞明白我线段树思路错在哪里了。
我的思路是如果一个已经有覆盖标记的节点，加的时候先下传覆盖标记再加；如果是一个已经有覆盖标记的节点，下传的时候不管加标记同时把加标记情空。
by Edgebright @ 2023-08-11 11:14:08
附上可以hack本代码的小数据
```cpp
12
8 12 4
10 1 4
8 9 5
9 10 5
12 4 7
11 12 10
12 6 10
5 6 12
8 7 12
2 3 13
4 2 16
Change 11 50
Cover 5 2 26
Change 2 34
Cover 2 1 12
Add 1 10 30
Cover 8 1 28
Add 7 2 13
Change 1 44
Cover 12 8 20
Change 8 40
Cover 8 2 19
Change 3 43
Change 5 45
Change 4 32
Cover 9 10 0
Add 12 9 30
Add 7 10 44
Cover 9 11 20
Add 9 4 8
Add 7 10 33
Max 12 9
Stop
```
正确输出：61，错误输出：53
by Edgebright @ 2023-08-11 11:15:16
还有一组
```cpp
7
4 2 1
3 5 1
2 6 1
3 6 1
7 5 1
4 1 2
Add 6 2 35
Cover 5 4 50
Change 1 36
Add 7 3 11
Cover 6 1 18
Add 1 6 30
Cover 1 7 40
Change 4 31
Add 4 3 14
Cover 2 4 50
Cover 7 4 19
Add 5 1 25
Cover 6 2 12
Cover 1 3 48
Change 6 41
Add 1 4 44
Add 6 2 27
Change 6 46
Cover 4 7 24
Cover 5 1 8
Change 4 49
Cover 4 2 2
Cover 7 1 22
Change 1 44
Cover 5 2 26
Change 1 37
Cover 1 6 30
Change 1 21
Change 3 41
Change 6 21
Add 4 7 38
Cover 4 1 24
Change 6 41
Change 3 21
Change 3 3
Cover 1 6 12
Add 3 7 50
Add 4 1 50
Cover 1 2 31
Change 6 44
Max 7 4
Stop
```
答案114，错误输出110
by Edgebright @ 2023-08-11 11:56:47
[AC记录](https://www.luogu.com.cn/record/121469279)
两个地方：
- 下放 tag 标记时不要把 add 标记赋值为0，因为一个线段树结点既有 tag 标记又有 add 标记就意味着这个区间内先被 Cover 又被 Add
- 你的 Cover 函数在操作时没有将 add 标记赋值为0
参考代码如下：
```cpp
#include<bits/stdc++.h>
#define __lg(x) ((x) ? __lg(x) : 0)
typedef long long ll;
using namespace std;
const int N = 100005, Lg = 20;
int dfn[N], hvy[N], sz[N], a[N], inv[N], top[N];
int anc[Lg][N], dep[N];
int id[N], inv_id[N];
int stp;
int n;
struct edge
{
int n, t, w, id;
}e[N << 1];
int h[N], ce;
inline void add(int u, int v, int w, int id)
{
e[++ce] = {h[u], v, w, id};
h[u] = ce; return;
}
void getsz(int u, int f)
{
sz[u] = 1;
anc[0][u] = f; dep[u] = dep[f] + 1;
for(int i = h[u]; i; i = e[i].n)
{
int to = e[i].t; if(to == f) continue;
a[to] = e[i].w;
id[to] = e[i].id;
getsz(to, u);
if(sz[to] > sz[hvy[u]])
{
hvy[u] = to;
}
sz[u] += sz[to];
}
return;
}
void decomp(int u, int f)
{
dfn[u] = ++stp;
top[u] = ((u == hvy[f]) ? top[f]: u);
if(hvy[u]) decomp(hvy[u], u);
for(int i = h[u]; i; i = e[i].n)
{
int to = e[i].t;
if(to == f || to == hvy[u]) continue;
decomp(to, u);
}
return;
}
void inverse()
{
for(int i = 1; i <= n; ++i)
{
inv[dfn[i]] = i;
}
for(int i = 1; i <= n; ++i)
{
inv_id[id[i]] = i;
}
}
struct nd
{
int l, r;
int mx, tag, add;
};
struct segt
{
nd s[N << 2];
inline void upd(int p)
{
s[p].mx = max(s[p<<1].mx, s[p<<1|1].mx);
}
inline void spread(int p)
{
if(s[p].tag != -1)
{
s[p<<1].tag = s[p<<1].mx = s[p].tag;
s[p<<1].add = 0;
s[p<<1|1].tag = s[p<<1|1].mx = s[p].tag;
s[p<<1|1].add = 0;
s[p].tag = -1;
}
if(s[p].add)
{
s[p<<1].add += s[p].add;
s[p<<1].mx += s[p].add;
s[p<<1|1].add += s[p].add;
s[p<<1|1].mx += s[p].add;
s[p].add = 0;
return;
}
}
void build(int p, int l, int r)
{
s[p].l = l; s[p].r = r;
s[p].tag = -1; s[p].add = 0;
if(l == r)
{
s[p].mx = a[inv[l]]; return;
}
int Md = (l + r) >> 1;
build(p<<1, l, Md);
build(p<<1|1, Md + 1, r);
upd(p); return;
}
void change(int p, int x, int w)
{
if(s[p].l == s[p].r)
{
s[p].mx = w; return;
}
spread(p);
int Md = (s[p].l + s[p].r) >> 1;
if(x <= Md) change(p<<1, x, w);
else change(p<<1|1, x, w);
upd(p);
return;
}
void cover(int p, int l, int r, int w)
{
if(l > r) return;
if(l <= s[p].l && s[p].r <= r)
{
s[p].mx = s[p].tag = w;
s[p].add = 0;
return;
}
spread(p);
int Md = (s[p].l + s[p].r) >> 1;
if(l <= Md) cover(p<<1, l, r, w);
if(r > Md) cover(p<<1|1, l ,r, w);
upd(p);
return;
}
void Add(int p, int l ,int r, int d)
{
if(l > r) return;
spread(p);
if(l <= s[p].l && s[p].r <= r)
{
s[p].mx += d; s[p].add += d; return;
}
int Md = (s[p].l + s[p].r) >> 1;
if(l <= Md) Add(p<<1, l, r, d);
if(r > Md) Add(p<<1|1, l, r, d);
upd(p);
return;
}
int query(int p, int l, int r)
{
if(l > r) return 0;
// printf("L%d R%d\n",l, r);
if(l <= s[p].l && s[p].r <= r)
{
return s[p].mx;
}
spread(p);
int mx = 0, Md = (s[p].l + s[p].r) >> 1;
if(l <= Md) mx = max(mx, query(p<<1, l, r));
if(r > Md) mx = max(mx, query(p<<1|1, l, r));
return mx;
}
};
segt t;
void get_anc()
{
for(int ex = 1; ex <= __lg(n); ++ex)
{
for(int i = 1; i <= n; ++i)
{
anc[ex][i] = anc[ex - 1][anc[ex - 1][i]];
}
}
return;
}
int get_lca(int u, int v)
{
if(dep[u] < dep[v]) swap(u, v);
while(dep[u] > dep[v])
{
u = anc[__lg(dep[u] - dep[v])][u];
}
if(u == v) return u;
for(int ex = __lg(dep[u]); ex >= 0; --ex)
{
if(anc[ex][u] == anc[ex][v]) continue;
u = anc[ex][u]; v = anc[ex][v];
}
return anc[0][u];
}
void chain_cover(int u, int v, int w)
{
if(dep[u] < dep[v]) swap(u, v);
while(dep[top[u]] > dep[v])
{
t.cover(1, dfn[top[u]], dfn[u], w);
u = anc[0][top[u]];
}
t.cover(1, dfn[v] + 1, dfn[u], w);
return;
}
void chain_add(int u, int v, int d)
{
if(dep[u] < dep[v]) swap(u, v);
while(dep[top[u]] > dep[v])
{
t.Add(1, dfn[top[u]], dfn[u], d);
u = anc[0][top[u]];
}
t.Add(1, dfn[v] + 1, dfn[u], d);
return;
}
int chain_qry(int u, int v)
{
if(dep[u] < dep[v]) swap(u, v);
int res = 0;
while(dep[top[u]] > dep[v])
{
res = max(res, t.query(1, dfn[top[u]], dfn[u]));
u = anc[0][top[u]];
}
res = max(res, t.query(1, dfn[v] + 1, dfn[u]));
return res;
}
signed main()
{
// freopen("tree.in", "r", stdin);
scanf("%d", &n);
for(int i = 1; i < n; ++i)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w, i); add(v, u, w, i);
}
getsz(1, 0);
decomp(1, 0);
inverse();
get_anc();
t.build(1, 1, n);
char op[7];//0_index
while(scanf("%s", op), op[2] != 'o')
{
if(op[2] == 'a')//change
{
int k, w; scanf("%d%d", &k, &w);
t.change(1, dfn[inv_id[k]], w);
}
else if(op[2] == 'v')//cover
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
int lca = get_lca(u, v);
chain_cover(lca, u, w);//(lca,u]
chain_cover(lca, v, w);
}
else if(op[2] == 'd')
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
int lca = get_lca(u, v);
chain_add(lca, u, w);//(lca,u]
chain_add(lca, v, w);
}
else if(op[2] == 'x')
{
int u, v, w;
scanf("%d%d", &u, &v);
int lca = get_lca(u, v);
// printf("lca%d\n", lca);
int mx = 0;
mx = max(mx, chain_qry(lca, u));
mx = max(mx, chain_qry(lca, v));
printf("%d\n", mx);
}
}
return 0;
}
```
by feather02 @ 2023-08-17 20:17:39
~~我排版炸了应该没关系吧~~
by feather02 @ 2023-08-17 20:19:36