......这题难道必要维护`size`？
by KokiNiwa @ 2020-05-01 20:12:49
@[skicean](/user/75715) 不用像哪题这么麻烦啊
by 奇米 @ 2020-05-01 20:17:53
@[奇米](/user/308464) 啥，这题不用维护`size`吧，您说哪题啊
by KokiNiwa @ 2020-05-01 20:23:07
@[skicean](/user/75715) 这道需要维护$siz$，但是只要pushup里更新即可
by 奇米 @ 2020-05-01 20:24:06
而那道题目还要记录：一个点的实际siz,以及虚点的个数
by 奇米 @ 2020-05-01 20:24:54
@[奇米](/user/308464) 那我就bzd了.../fad 我那题用树剖写的
by KokiNiwa @ 2020-05-01 21:01:56
@[skicean](/user/75715) 那你能帮助我改改错吗？tks
by 奇米 @ 2020-05-01 21:06:28
```cpp
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
inline int read()
{
int sum=0,ff=1; char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') ff=-1;
ch=getchar();
}
while(isdigit(ch))
sum=sum*10+(ch^48),ch=getchar();
return sum*ff;
}
const int N=1e5+5;
const int mo=51061;
int n,m,stak[N],siz[N],top;
struct Node
{
int fa,ch[2],val,sum;
int mul,add,laz;
};
Node t[N];
inline void Add(int &x,int y)
{
x+=y;
if(x>=mo) x%=mo;
}
struct LCT
{
inline void pushup(int x)
{
int ls=t[x].ch[0];
int rs=t[x].ch[1];
siz[x]=siz[ls]+siz[rs]+1;
t[x].sum=(t[ls].sum+t[rs].sum+t[x].val)%mo;
}
inline void pushadd(int x,int val)
{
Add(t[x].sum,siz[x]*val);
Add(t[x].val,val);
Add(t[x].add,val);
}
inline void pushmul(int x,int val)
{
t[x].sum=(t[x].sum*val)%mo;
t[x].val=(t[x].val*val)%mo;
t[x].mul=(t[x].mul*val)%mo;
t[x].add=(t[x].add*val)%mo;
}
inline void pushdown(int x)
{
if(t[x].add)
{
int ls=t[x].ch[0];
int rs=t[x].ch[1];
pushadd(ls,t[x].add);
pushadd(rs,t[x].add);
t[x].add=0;
}
if(t[x].mul!=1ll)
{
int ls=t[x].ch[0];
int rs=t[x].ch[1];
pushmul(ls,t[x].mul);
pushmul(rs,t[x].mul);
t[x].mul=1;
}
if(t[x].laz)
{
swap(t[x].ch[0],t[x].ch[1]);
t[t[x].ch[0]].laz^=1;
t[t[x].ch[1]].laz^=1;
t[x].laz=0;
}
}
inline bool pd(int x)
{
return t[t[x].fa].ch[0]!=x&&t[t[x].fa].ch[1]!=x;
}
inline void rotate(int x)
{
int y=t[x].fa;
int z=t[y].fa;
int k=t[y].ch[1]==x;
if(!pd(y)) t[z].ch[y==t[z].ch[1]]=x;
t[x].fa=z;
t[y].ch[k]=t[x].ch[k^1];
t[t[x].ch[k^1]].fa=y;
t[x].ch[k^1]=y;
t[y].fa=x;
pushup(y);
pushup(x);
}
inline void splay(int x)
{
stak[top=1]=x;
for ( int i=x;!pd(i);i=t[i].fa ) stak[++top]=t[i].fa;
for ( int i=top;i;i--) pushdown(stak[i]);
while(!pd(x))
{
int y=t[x].fa,z=t[y].fa;
if(!pd(y))
(t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);
rotate(x);
}
pushup(x);
}
inline void access(int x)
{
for ( int y=0;x;y=x,x=t[x].fa )
splay(x),t[x].ch[1]=y,pushup(x);
}
inline void makert(int x)
{
access(x);
splay(x);
t[x].laz^=1;
}
inline int findrt(int x)
{
access(x);
splay(x);
while(t[x].ch[0]) pushdown(x),x=t[x].ch[0];
splay(x);
return x;
}
inline void split(int x,int y)
{
makert(x);
access(y);
splay(y);
}
inline void cut(int x,int y)
{
makert(x);
if(findrt(y)==x&&t[y].fa==x&&!t[y].ch[0])
{
t[y].fa=0;
t[x].ch[1]=0;
pushup(x);
}
}
inline void link(int x,int y)
{
makert(x);
makert(y);
if(findrt(x)==findrt(y)) return;
t[x].fa=y;
pushup(y);
}
};
LCT T;
signed main()
{
freopen("a.in","r",stdin);
n=read();
m=read();
for ( int i=1;i<=n;i++ )
t[i].val=t[i].mul=siz[i]=1;
for ( int i=1;i<n;i++ )
{
int x,y;
x=read(),y=read();
T.link(x,y);
}
for (;m--;)
{
char op[3];
int x,y;
scanf("%s",op+1);
x=read(),y=read();
if(op[1]=='+')
{
T.split(x,y);
int v=read();
T.pushadd(y,v);
}
if(op[1]=='-')
{
int xx=read(),yy=read();
T.cut(x,y);
T.link(xx,yy);
}
if(op[1]=='*')
{
int val=read();
T.split(x,y);
T.pushmul(y,val);
}
if(op[1]=='/')
{
T.split(x,y);
printf("%lld\n",t[y].sum);
}
}
return 0;
}
```
by 奇米 @ 2020-05-01 21:06:40
只有5分
by 奇米 @ 2020-05-01 21:06:51
改好了
by 奇米 @ 2020-05-01 21:09:34