1. 题目

传送门=￣ω￣=

上面那个是个权限题，所以木有权限的童鞋们可以去清橙上刷：传送门=￣ω￣=

或者可以去 LUOGU 上刷：传送门=￣ω￣=

2. 题解

看到 boshi 正在刷 lct 于是赶紧跟风 QvQ

好久没写 lct 的题了 QvQ，感觉现在复习一下还是很吼滴！

就搞个 lct，里面的 splay 支持乘法、加法标记就行了。

两个标记优先搞乘法，再搞加法。

还有就是会爆 ing，而开 long long 会超时，所以。。。反正没负数，用 unsigned int 就行了。

代码应该还算通俗易懂吧 QvQ

代码：

#include <bits/stdc++.h>
#define MOD (51061)
#define NS (100005)
using namespace std;
typedef unsigned int UI;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
UI n,q;
char opt[5];
stack<UI> st;
struct N{UI f,s[2],rev,sz,sum,d,ptag,mtag;}e[NS];
void M(UI a)
{
    e[a].sum%=MOD,e[a].d%=MOD;
    e[a].ptag%=MOD,e[a].mtag%=MOD,e[a].sz%=MOD;
}
bool pos(UI a){return e[e[a].f].s[1]==a;}
bool isroot(UI a){return e[e[a].f].s[0]!=a&&e[e[a].f].s[1]!=a;}
void pup(UI a)
{
    UI l=e[a].s[0],r=e[a].s[1];
    e[a].sz=e[l].sz+e[r].sz+1;
    e[a].sum=e[l].sum+e[r].sum+e[a].d;
    M(a);
}
void pdown(UI a)
{
    UI l=e[a].s[0],r=e[a].s[1],t;
    if(t=e[a].mtag,t!=1)
    {
        if(l)e[l].d*=t,e[l].ptag*=t,e[l].mtag*=t,e[l].sum*=t,M(l);
        if(r)e[r].d*=t,e[r].ptag*=t,e[r].mtag*=t,e[r].sum*=t,M(r);
        e[a].mtag=1;
    }
    if(t=e[a].ptag,t)
    {
        if(l)e[l].d+=t,e[l].ptag+=t,e[l].sum+=e[l].sz*t,M(l);
        if(r)e[r].d+=t,e[r].ptag+=t,e[r].sum+=e[r].sz*t,M(r);
        e[a].ptag=0;
    }
    if(e[a].rev)
    {
        if(l)e[l].rev^=1,swap(e[l].s[0],e[l].s[1]);
        if(r)e[r].rev^=1,swap(e[r].s[0],e[r].s[1]);
        e[a].rev=0;
    }
}
void rot(UI a)
{
    UI f=e[a].f,g=e[f].f,p=pos(a);
    if(!isroot(f))e[g].s[pos(f)]=a;
    e[a].f=g,e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    pup(f),pup(a);
}
void splay(UI a)
{
    st.push(a);
    for(UI i=a;!isroot(i);i=e[i].f)st.push(e[i].f);
    while(!st.empty())pdown(st.top()),st.pop();
    for(;!isroot(a);rot(a))if(!isroot(e[a].f))
        if(pos(a)^pos(e[a].f))rot(a);
        else rot(e[a].f);
}
void acc(UI a){for(UI b=0;a;a=e[a].f)splay(a),e[a].s[1]=b,pup(a),b=a;}
void evert(UI a){acc(a),splay(a),e[a].rev^=1,swap(e[a].s[0],e[a].s[1]);}
void link(UI a,UI b){evert(a),e[a].f=b;}
void cut(UI a,UI b){evert(b),acc(a),splay(a),e[a].s[0]=e[b].f=0;}
void split(UI a,UI b){evert(b),acc(a),splay(a);}
int main()
{
    IN(n),IN(q);
    for(UI i=1;i<=n;i++)e[i].sz=e[i].d=e[i].sum=e[i].mtag=1;
    for(UI i=1,u,v;i<n;i++)IN(u),IN(v),link(u,v);
    while(q--)
    {
        UI a,b,c,d;
        if(scanf("%s",opt),IN(a),IN(b),opt[0]=='+')
            IN(c),c%=MOD,split(a,b),e[a].d+=c,e[a].ptag+=c,M(a);
        else if(opt[0]=='*')
            IN(c),c%=MOD,split(a,b),e[a].d*=c,e[a].ptag*=c,e[a].mtag*=c,M(a);
        else if(opt[0]=='-')IN(c),IN(d),cut(a,b),link(c,d);
        else split(a,b),printf("%u\n",e[a].sum);
    }
    return 0;
}