我怀疑是我 $\rm addlazy$ 写错了但我没有证据
by zhoukangyang @ 2020-07-15 19:20:14
@[zhoukangyang](/user/173660) 线段树模板2上动态树?
by FunnyCreatress @ 2020-07-15 19:34:02
@[FunnyCreatress](/user/77174) 谔谔,好像是的 ~~我绝对不会告诉你线段树2我用了平衡树,普通线段树,标记永久化都没做过去~~
by zhoukangyang @ 2020-07-15 19:35:32
~~所以这次想用LCT~~
by zhoukangyang @ 2020-07-15 19:35:53
@[zhoukangyang](/user/173660)
```
ans[id] = (ans[id] * x + y) % mod;
```
为什么是`+y`不是`+y*len(id)`
by FunnyCreatress @ 2020-07-15 19:36:36
@[FunnyCreatress](/user/77174) 啊谢谢好像是的我去改改
by zhoukangyang @ 2020-07-15 19:37:18
@[FunnyCreatress](/user/77174) 谢谢,过了
```
#include<bits/stdc++.h>
#define N 114514
#define mod 51061
#define ls ch[x][0]
#define rs ch[x][1]
#define uint unsigned int
using namespace std;
int ch[N][2],fa[N],flag[N];
uint lazya[N],lazyb[N],ans[N],siz[N],val[N];
int get(int x) {
return (ch[fa[x]][0] == x || ch[fa[x]][1] == x);
}
void flip(int x) {
if(x) swap(ch[x][0],ch[x][1]),flag[x]^=1;
}
void addlazy(int id,uint x,uint y) {
if(!id) return;
ans[id] = (ans[id] * x + siz[id] * y) % mod;
lazya[id] = lazya[id] * x % mod;
lazyb[id] = (lazyb[id] * x + y) % mod;
val[id] = (val[id] * x + y) % mod;
}
void pushdown(int x) {
addlazy(ls,lazya[x],lazyb[x]),addlazy(rs,lazya[x],lazyb[x]);
lazya[x] = 1, lazyb[x] = 0;
if(flag[x]) flip(ls),flip(rs),flag[x] = 0;
}
void upd(int x) {
pushdown(x),ans[x] = (ans[ls] + ans[rs] + val[x]) % mod;
siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
}
void rotate(int x) {
int y = fa[x], z = fa[y], fson = (ch[y][1] == x), ano = ch[x][1^fson];
if(get(y)) ch[z][ch[z][1]==y] = x;
if(ano) fa[ano] = y;
fa[y] = x, ch[x][1^fson] = y, fa[x] = z, ch[y][fson] = ano;
upd(y),upd(x);
}
int fx,tot,f[N];
void Splay(int x) {
tot = 1, f[tot] = fx = x;
while(get(fx)) ++tot, f[tot] = fx = fa[fx];
while(tot) pushdown(f[tot]), tot--;
while(get(x)) {
int y = fa[x], z = fa[y];
if(get(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
rotate(x);
}
upd(x);
}
void access(int x) {
int y = 0;
while(x) {
Splay(x);
ch[x][1] = y;
upd(x);
y = x;
x = fa[x];
}
}
void makeroot(int x) {
access(x),Splay(x),flip(x);
}
int findroot(int x) {
access(x),Splay(x), pushdown(x);
while(ch[x][0]) x = ch[x][0], pushdown(x);
Splay(x);
return x;
}
void split(int x,int y) {
makeroot(x),access(y),Splay(y);
}
void link(int x,int y) {
makeroot(x);
if(findroot(y) != x) findroot(y), fa[x] = y;
}
void cut(int x,int y) {
makeroot(x);
if(findroot(y) == x && fa[y] == x && !ch[y][0]) fa[y] = ch[x][1] = 0, upd(x);
}
int n,m,s,x,y,z;
char opt[1000];
signed main() {
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) ans[i] = val[i] = lazya[i] = siz[i] = 1;
for(int i = 1; i < n; i++) {
scanf("%d%d",&x,&y);
link(x,y);
}
while(m--) {
scanf("%s%d%d",opt,&x,&y);
if(opt[0] == '+') scanf("%d",&z),split(x,y),addlazy(y,1,z);
if(opt[0] == '-') scanf("%d%d",&s,&z),cut(x,y),link(s,z);
if(opt[0] == '*') scanf("%d",&z),split(x,y),addlazy(y,z,0);
if(opt[0] == '/') split(x,y),printf("%d\n",ans[y]);
}
return 0;
}
```
by zhoukangyang @ 2020-07-15 19:39:23
去切线段树2啦/cy
by zhoukangyang @ 2020-07-15 19:39:46
@[zhoukangyang](/user/173660) 蓝题以上求助成功的帖子好久没看到了qwq
by FunnyCreatress @ 2020-07-15 19:45:25
@[FunnyCreatress](/user/77174) qwq因为您是大佬啊
by zhoukangyang @ 2020-07-15 19:46:52