题目链接：
题目分析
LCT，像线段树区间乘，区间加那样打标记。
这道题我调了一下午。
提交之后TLE了，我一直以为是写错了导致了死循环。
于是一直在排查错误。直到..
直到我看了hzwer的博客，就一句话：“其实这题不需要开long long。。。只要unsigned int，不然可能会T”。
纳尼？！TLE是因为常数问题？于是我将 long long 改成了 unsighed int ，然后...AC。
我................！
long long 不能随便用啊...
代码
#include#include #include #include #include #include using namespace std;inline void Read(int &Num){ char c = getchar(); bool Neg = false; while (c < '0' || c > '9') { if (c == '-') Neg = true; c = getchar(); } Num = c - '0'; c = getchar(); while (c >= '0' && c <= '9') { Num = Num * 10 + c - '0'; c = getchar(); } if (Neg) Num = -Num;}const int MaxN = 100000 + 5, Mod = 51061;typedef unsigned int LL;int n, q;int Father[MaxN], Son[MaxN][2], Size[MaxN];LL T[MaxN], Mul[MaxN], Plus[MaxN], A[MaxN]; bool Rev[MaxN], isRoot[MaxN];inline void Update(int x){ T[x] = (T[Son[x][0]] + T[Son[x][1]] + A[x]) % Mod; Size[x] = Size[Son[x][0]] + Size[Son[x][1]] + 1;}inline void Reverse(int x){ Rev[x] = !Rev[x]; swap(Son[x][0], Son[x][1]);}inline void Paint_Mul(int x, LL Num){ Mul[x] = Mul[x] * Num % Mod; Plus[x] = Plus[x] * Num % Mod; T[x] = T[x] * Num % Mod; A[x] = A[x] * Num % Mod;}inline void Paint_Plus(int x, LL Num){ Plus[x] = (Plus[x] + Num) % Mod; T[x] = (T[x] + Num * Size[x] % Mod) % Mod; A[x] = (A[x] + Num) % Mod;}inline void PushDown(int x){ if (Rev[x]) { Rev[x] = false; if (Son[x][0]) Reverse(Son[x][0]); if (Son[x][1]) Reverse(Son[x][1]); } if (Mul[x] != 1) { if (Son[x][0]) Paint_Mul(Son[x][0], Mul[x]); if (Son[x][1]) Paint_Mul(Son[x][1], Mul[x]); Mul[x] = 1; } if (Plus[x] != 0) { if (Son[x][0]) Paint_Plus(Son[x][0], Plus[x]); if (Son[x][1]) Paint_Plus(Son[x][1], Plus[x]); Plus[x] = 0; }}void Rotate(int x){ int y = Father[x], f; PushDown(y); PushDown(x); if (x == Son[y][0]) f = 1; else f = 0; if (isRoot[y]) { isRoot[y] = false; isRoot[x] = true; } else { if (y == Son[Father[y]][0]) Son[Father[y]][0] = x; else Son[Father[y]][1] = x; } Father[x] = Father[y]; Son[y][f ^ 1] = Son[x][f]; if (Son[x][f]) Father[Son[x][f]] = y; Son[x][f] = y; Father[y] = x; Update(y); Update(x);}void Splay(int x){ int y; while (!isRoot[x]) { y = Father[x]; if (isRoot[y]) { Rotate(x); break; } if (y == Son[Father[y]][0]) { if (x == Son[y][0]) { Rotate(y); Rotate(x); } else { Rotate(x); Rotate(x); } } else { if (x == Son[y][1]) { Rotate(y); Rotate(x); } else { Rotate(x); Rotate(x); } } }}int Access(int x){ int y = 0; while (x != 0) { Splay(x); PushDown(x); if (Son[x][1]) isRoot[Son[x][1]] = true; Son[x][1] = y; if (y) isRoot[y] = false; Update(x); y = x; x = Father[x]; } return y;}void Make_Root(int x){ int t = Access(x); Reverse(t);}int main(){ scanf("%d%d", &n, &q); int a, b; for (int i = 1; i <= n; ++i) { A[i] = T[i] = 1; Mul[i] = 1; Plus[i] = 0; isRoot[i] = true; Size[i] = 1; } for (int i = 1; i <= n - 1; ++i) { Read(a); Read(b); Make_Root(a); Splay(a); Father[a] = b; } char Str[5]; int x, y, Num, t; for (int i = 1; i <= q; ++i) { scanf("%s", Str); switch (Str[0]) { case '+' : Read(x); Read(y); Read(Num); Make_Root(x); t = Access(y); Paint_Plus(t, (LL)Num); break; case '-' : Read(x); Read(y); Make_Root(x); Access(y); Splay(y); PushDown(y); isRoot[Son[y][0]] = true; Father[Son[y][0]] = 0; Son[y][0] = 0; Update(y); Read(x); Read(y); Make_Root(x); Splay(x); Father[x] = y; break; case '*' : Read(x); Read(y); Read(Num); Make_Root(x); t = Access(y); Paint_Mul(t, (LL)Num); break; case '/' : Read(x); Read(y); Make_Root(x); t = Access(y); printf("%d\n", (int)(T[t] % Mod)); break; } } return 0;}