题面:
1.树链加;
2.删边加边;
3.树链乘;
4.树链和查询。
还是lct的题。只是标记下传时比较坑。
代码:
#include<cstdio> #include<algorithm> using namespace std; #define MOD 51061 #define N 100050 #define ui unsigned int ui n,m; ui fa[N],ch[N][2],vl[N],sum[N],siz[N],mk1[N],mk2[N]; bool res[N],rt[N]; inline ui rd() { ui f = 1,c = 0;char ch = getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch = getchar();} while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch = getchar();} return f*c; } void reser(ui x) { swap(ch[x][0],ch[x][1]); res[x]^=1; } void add(ui x,ui d) { vl[x] = (vl[x]+d)%MOD; mk1[x]=(mk1[x] + d)%MOD; } void mul(ui x,ui d) { vl[x] = (vl[x]*d)%MOD; mk2[x]=(mk2[x] * d)%MOD; } void update(ui x) { siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1; sum[x] = ((((sum[ch[x][0]] + sum[ch[x][1]])%MOD)*mk2[x]%MOD + (siz[x]-1)*mk1[x]%MOD)%MOD + vl[x])%MOD; } void cal(ui x,ui a,ui b) { vl[x] = (vl[x]*b%MOD + a%MOD)%MOD; sum[x] = (sum[x]*b%MOD + siz[x]*a%MOD)%MOD; mk1[x] = (mk1[x]*b%MOD + a)%MOD; mk2[x] = (mk2[x]*b)%MOD; } void pushdown(ui x) { if(res[x]) { reser(ch[x][0]); reser(ch[x][1]); res[x]=0; } /* if(mk1[x]) { add(ch[x][0],mk1[x]); add(ch[x][1],mk1[x]); mk1[x]=0; } if(mk2[x]!=1) { mul(ch[x][0],mk2[x]); mul(ch[x][1],mk2[x]); mk2[x]=1; }*/ if(mk1[x]||mk2[x]!=1) { cal(ch[x][0],mk1[x],mk2[x]); cal(ch[x][1],mk1[x],mk2[x]); mk1[x]=0,mk2[x]=1; } } void down(ui x) { if(!rt[x])down(fa[x]); pushdown(x); } void rotate(ui x) { ui y = fa[x],k = (ch[y][1]==x); if(rt[y])rt[y]=0,rt[x]=1; else ch[fa[y]][ch[fa[y]][1]==y] = x; fa[x] = fa[y]; ch[y][k] = ch[x][!k],fa[ch[x][!k]] = y; ch[x][!k] = y,fa[y] = x; update(y),update(x); } void splay(ui x) { down(x); while(!rt[x]) { ui y = fa[x],z = fa[y]; if(!rt[y]) ((ch[y][1]==x)^(ch[z][1]==y))?rotate(x):rotate(y); rotate(x); } } void access(ui x) { ui y = 0; while(x) { splay(x); rt[ch[x][1]] = 1,rt[y] = 0; ch[x][1] = y; update(x); y = x,x = fa[x]; } } void mtr(ui x) { access(x); splay(x); reser(x); } void link(ui x,ui y) { mtr(x); fa[x] = y; } void cut(ui x,ui y) { mtr(x); access(y); splay(y); ch[y][0] = fa[x] = 0; rt[x]=1; } void jia(ui u,ui v,ui c) { mtr(u); access(v); splay(u); add(u,c); } void cheng(ui u,ui v,ui c) { mtr(u); access(v); splay(u); mul(u,c); } ui query(ui u,ui v) { mtr(u); access(v); splay(u); return sum[u]; } int main() { n = rd(),m = rd(); for(ui i=1;i<=n;i++)vl[i] = mk2[i] = siz[i] = 1,rt[i] = 1; ui u,v,c; char cc[2]; for(ui i=1;i<n;i++) { u=rd(),v=rd(); link(u,v); } for(ui i=1;i<=m;i++) { scanf("%s",cc); if(cc[0]=='+') { u=rd(),v=rd(),c=rd(); jia(u,v,c); }else if(cc[0]=='-') { u=rd(),v=rd(); cut(u,v); u=rd(),v=rd(); link(u,v); }else if(cc[0]=='*') { u=rd(),v=rd(),c=rd(); cheng(u,v,c); }else { u=rd(),v=rd(); printf("%u ",query(u,v)); } } return 0; }