@Dorbmon 2020-01-31 22:04 回复 真的只有5分!!!!求助!!!!!!!!! #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1000000; bool fan [N];int son [2][N];int fa [N]; ll val [N]; ll rsize [N]; ll sum [N]; inline void push_up (int x) { rsize [x] = rsize [son [0][x]] + rsize [son [1][x]] + 1; sum [x] = sum [son [0][x]] + sum [son [1][x]] + val [x]; } ll tag [2][N]; const ll MOD = 51061; //1加 //0乘法 default:1 inline void push_down (int x) { if (son [0][x]) { sum [son [0][x]] *= tag [0][x]; sum [son [0][x]] %= MOD; sum [son [0][x]] += tag [1][x] * rsize [son [0][x]]; sum [son [0][x]] %= MOD; val [son [0][x]] *= tag [0][x]; val [son [0][x]] %= MOD; val [son [0][x]] += tag [1][x]; val [son [0][x]] %= MOD; tag [0][son [0][x]] *= tag [0][x]; tag [0][son [0][x]] %= MOD; tag [1][son [0][x]] *= tag [0][x]; tag [1][son [0][x]] %= MOD; tag [1][son [0][x]] += tag [1][x]; tag [1][son [0][x]] %= MOD; } if (son [1][x]) { sum [son [1][x]] *= tag [0][x]; sum [son [1][x]] %= MOD; sum [son [1][x]] += tag [1][x] * rsize [son [1][x]]; sum [son [1][x]] %= MOD; val [son [1][x]] *= tag [0][x]; val [son [1][x]] %= MOD; val [son [1][x]] += tag [1][x]; val [son [1][x]] %= MOD; tag [0][son [1][x]] *= tag [0][x]; tag [0][son [1][x]] %= MOD; tag [1][son [1][x]] *= tag [0][x]; tag [1][son [1][x]] %= MOD; tag [1][son [1][x]] += tag [1][x]; tag [1][son [1][x]] %= MOD; } tag [1][x] = 0; tag [0][x] = 1; if (fan [x]) { fan [son [1][x]] ^= 1; swap (son [0][son [1][x]],son [1][son [1][x]]); fan [son [0][x]] ^= 1; swap (son [0][son [0][x]],son [1][son [0][x]]); fan [x] = false; } } inline int get (int x) { return (son [1][fa [x]] == x); } inline bool is_root (int x) { return ((!fa [x]) || (son [get (x)][fa [x]] != x)); } inline void connect (int a,int b,int d) { if (a) { fa [a] = b; } if (b) { son [d][b] = a; push_up (b); } } inline void rorate (int x) { //上旋 int f = fa [x],ff = fa [f],d = get (x),e = get (f); if (is_root (x)) { return ; } if (!is_root (f)) { son [e][ff] = x; } fa [x] = ff; son [d][f] = son [d^1][x]; if (son [d^1][x]) { fa [son [d^1][x]] = f; } fa [f] = x; son [d^1][x] = f; push_up (f); push_up (x); } int buf [N]; inline void splay (int x) { int y = x,z = 0; buf [++ z] = y; while (!is_root (y)) { buf [++ z] = (y = fa [y]); //cout << buf [z] << endl; } while (z) { push_down (buf [z --]); } for (int f = fa [x];!is_root (x) && (f = fa [x]);rorate (x)) { if (fa [f]) { rorate ((get (f) == get (x))?f:x); } } push_up (x); } inline void access (int x) { int y = 0; while (x) { //cout << x; splay (x); son [1][x] = y; push_up (x); y = x; x = fa [x]; } } inline void make_root (int x) { access (x);splay (x); swap (son [0][x],son [1][x]);fan [x] ^= 1; return ; } inline void split (int a,int b) { make_root (a); //因为深度一样的不可能在一棵splay中。 access (b); splay (b); } inline int find_root (int x) { access (x); splay (x); while (son [0][x]) push_down (x),x = son [0][x]; return x; } inline void cut (int u,int v) { split (u,v); //v为根 并且u是根了 //所以u一定在v的最左儿子上 if (find_root (v) == u && fa [u] == v && !son [1][u]) { son [0][v] = fa [u] = 0; push_up (v); } } int main(){ #ifndef ONLINE_JUDGE freopen ("shit.txt","r",stdin); #endif ios::sync_with_stdio (false); int n,q;cin >> n >> q; for (int i = 1;i <= n;++ i) { rsize [i] = sum [i] = val [i] = tag [0][i] = 1; } for (int i = 1;i <= n - 1;++ i) { int u,v;cin >> u >> v; //连接u,v make_root (v); fa [v] = u; } while (q --) { char opt;cin >> opt; //cout << opt << endl; if (opt == '+') { ll u,v,c;cin >> u >> v >> c; c %= MOD; split (u,v); val [v] += c; val [v] %= MOD; sum [v] += rsize [v] * c; sum [v] %= MOD; tag [1][v] += c; tag [1][v] %= MOD; } else if (opt == '*') { ll u,v,c;cin >> u >> v >> c; split (u,v); val [v] *= c; val [v] %= MOD; sum [v] *= c; sum [v] %= MOD; tag [1][v] *= c; tag [1][v] %= MOD; tag [0][v] *= c; tag [0][v] %= MOD; } else if (opt == '-') { int u1,v1,u2,v2;cin >> u1 >> v1 >> u2 >> v2; cut (u1,v1); make_root (u2); access (v2); if (find_root (v2) != u2) { fa [u2] = v2; } } else if (opt == '/'){ int u,v;cin >> u >> v; split (u,v); cout << sum [v] << endl; } } return 0; }
真的只有5分!!!!求助!!!!!!!!!