题目
一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一：
+ u v c：将u到v的路径上的点的权值都加上自然数c； - u1 v1 u2 v2：将树中原有的边(u1,v1)删除，加入一条新边(u2,v2)，保证操作完之后仍然是一棵树； * u v c：将u到v的路径上的点的权值都乘上自然数c； / u v：询问u到v的路径上的点的权值和，求出答案对于51061的余数。输入格式
第一行两个整数n，q
接下来n-1行每行两个正整数u，v，描述这棵树 接下来q行，每行描述一个操作输出格式
对于每个/对应的答案输出一行
输入样例
3 2
1 2
2 3
- 1 3 4
/ 1 1
输出样例
4
题解
好久没敲LCT了。都快忘了【本来也没敲过几次】
一道很裸的板题，只是标记多了些，不过也是很经典的乘法 + 加法标记#include#include #include #include #define LL long long int#define REP(i,n) for (int i = 1; i <= (n); i++)#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)#define isrt(u) (!e[u].f || (e[e[u].f].ch[0] != u && e[e[u].f].ch[1] != u))#define isr(u) (e[e[u].f].ch[1] == u)#define ls e[u].ch[0]#define rs e[u].ch[1]using namespace std;const int maxn = 100005,maxm = 200005,INF = 1000000000,P = 51061;inline int RD(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57) { out = (out << 1) + (out << 3) + c - '0'; c = getchar();} return out * flag;}int h[maxn],ne = 0,N,Q;struct EDGE{int to,nxt;}ed[maxm];struct node{LL ch[2],f,plu,tim,w,sum,rev,siz;}e[maxn];inline void build(int u,int v){ ed[ne] = (EDGE){v,h[u]}; h[u] = ne++; ed[ne] = (EDGE){u,h[v]}; h[v] = ne++;}void pup(int u){ e[u].sum = (e[u].w + e[ls].sum + e[rs].sum) % P; e[u].siz = e[ls].siz + e[rs].siz + 1;}void pd(int u){ if (e[u].tim != 1){ e[ls].w = e[ls].w * e[u].tim % P; e[rs].w = e[rs].w * e[u].tim % P; e[ls].sum = e[ls].sum * e[u].tim % P; e[rs].sum = e[rs].sum * e[u].tim % P; e[ls].plu = e[ls].plu * e[u].tim % P; e[rs].plu = e[rs].plu * e[u].tim % P; e[ls].tim = e[ls].tim * e[u].tim % P; e[rs].tim = e[rs].tim * e[u].tim % P; } if (e[u].plu){ e[ls].w = (e[ls].w + e[u].plu) % P; e[rs].w = (e[rs].w + e[u].plu) % P; e[ls].sum = (e[ls].sum + (LL)e[ls].siz * e[u].plu % P) % P; e[rs].sum = (e[rs].sum + (LL)e[rs].siz * e[u].plu % P) % P; e[ls].plu = (e[ls].plu + e[u].plu) % P; e[rs].plu = (e[rs].plu + e[u].plu) % P; } if (e[u].rev){ swap(ls,rs); e[ls].rev ^= 1; e[rs].rev ^= 1; } e[u].plu = e[u].rev = 0; e[u].tim = 1;}void push_down(int u){if (!isrt(u)) push_down(e[u].f); pd(u);}void spin(int u){ int s = isr(u),fa = e[u].f; e[u].f = e[fa].f; if (!isrt(fa)) e[e[fa].f].ch[isr(fa)] = u; e[fa].ch[s] = e[u].ch[s ^ 1]; if (e[u].ch[s ^ 1]) e[e[u].ch[s ^ 1]].f = fa; e[fa].f = u; e[u].ch[s ^ 1] = fa; pup(fa);pup(u);}void splay(int u){ push_down(u); while (!isrt(u)){ if (isrt(e[u].f)) spin(u); else if (isr(u) ^ isr(e[u].f)) spin(u),spin(u); else spin(e[u].f),spin(u); }}void Access(int u){ int v = 0; while (u) splay(u),rs = v,e[v].f = u,pup(u),u = e[v = u].f;}void Make_root(int u){Access(u); splay(u); e[u].rev ^= 1;}void Link(int u,int v){ Make_root(u); Access(v); splay(v); e[u].f = v; pup(v);}void Cut(int u,int v){ Make_root(u); Access(v); splay(v); e[v].ch[0] = e[u].f = 0; pup(v);}LL Query(int u,int v){ Make_root(u); Access(v); splay(v); return e[v].sum;}void Add(int u,int v,LL w){ Make_root(u); Access(v); splay(v); e[v].w = (e[v].w + w) % P; e[v].plu = (e[v].plu + w) % P; e[v].sum = (e[v].sum + (LL)w * e[v].siz % P) % P;}void Tim(int u,int v,LL w){ Make_root(u); Access(v); splay(v); e[v].w = (e[v].w * w) % P; e[v].sum = (e[v].sum * w) % P; e[v].tim = (e[v].tim * w) % P; e[v].plu = (e[v].plu * w) % P;}void dfs(int u){ Redge(u) if (ed[k].to != e[u].f){ e[ed[k].to].f = u; dfs(ed[k].to); }}int main(){ memset(h,-1,sizeof(h)); N = RD(); Q = RD(); REP(i,N - 1) build(RD(),RD()); REP(i,N) e[i].sum = e[i].w = e[i].tim = e[i].siz = 1; dfs(1); char opt; int u,v,u1,v1; while (Q--){ opt = getchar(); while (opt != '+' && opt != '-' && opt != '*' && opt != '/') opt = getchar(); u = RD(); v = RD(); if (opt == '+') Add(u,v,RD()); else if (opt == '-') u1 = RD(),v1 = RD(),Cut(u,v),Link(u1,v1); else if (opt == '*') Tim(u,v,RD()); else if (opt == '/') printf("%lld\n",Query(u,v)); } return 0;}