Submit Info #17885

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp (anonymous) AC 412 ms 7.05 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.68 MiB
max_random_00 AC 405 ms 7.01 MiB
max_random_01 AC 394 ms 7.05 MiB
max_random_02 AC 412 ms 7.04 MiB
random_00 AC 256 ms 4.81 MiB
random_01 AC 286 ms 5.50 MiB
random_02 AC 153 ms 2.67 MiB
random_03 AC 169 ms 5.43 MiB
random_04 AC 97 ms 1.55 MiB
small_00 AC 2 ms 0.67 MiB
small_01 AC 1 ms 0.65 MiB
small_02 AC 2 ms 0.67 MiB

#include<bits/stdc++.h> using namespace std; // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/detail/standard_policies.hpp> // using namespace __gnu_pbds; #pragma GCC optimize("O3") #ifdef LOCAL #include "/Users/lbjlc/Desktop/coding/debug_utils.h" #else #define print(...) ; #define printn(...) ; #define printg(...) ; #define fprint(...) ; #define fprintn(...) ; #endif #define rep(i, a, b) for(auto i = (a); i < (b); i++) #define rrep(i, a, b) for(auto i = (a); i > (b); i--) #define all(v) (v).begin(), (v).end() #define pb push_back // #define mp make_pair #define fi first #define se second #define maxi(x, y) x = max(x, y) #define mini(x, y) x = min(x, y) // long long fact(long long n) { if(!n) return 1; return n*fact(n-1); } // #define endl '\n' mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define solve_testcase int T;cin>>T;for(int t=1;t<=T;t++){solve(t);} typedef unsigned long long ull; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<vvi> vvvi; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<pdd> vpdd; typedef vector<long long> vll; #define bd(type,op,val) bind(op<type>(), std::placeholders::_1, val) template<class T> void make_unique(T & v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); } int geti() { int x; cin >> x; return x; } long long getll() { long long x; cin >> x; return x; } double getd() { double x; cin >> x; return x; } // pair<int, int> a(geti(), geti()) does not work // pair<int, int> a({geti(), geti()}) works, since it uses initializer. const int MAXN = 5e5+50; int f[MAXN], c[MAXN][2], st[MAXN]; bool r[MAXN]; long long v[MAXN], s[MAXN]; // update node information void update(int x) { s[x] = s[c[x][0]] + s[c[x][1]] + v[x]; } // reverse x's subtree lazily void lazy_rev(int x) { swap(c[x][0], c[x][1]); r[x] ^= 1; } // push the lazy flag if exists void push_rev(int x) { if(r[x]) { if(c[x][0]) lazy_rev(c[x][0]); if(c[x][1]) lazy_rev(c[x][1]); r[x] = 0; } } // return true if x is NOT root of its splay. bool nroot(int x) { return c[f[x]][0] == x || c[f[x]][1] == x; } // splay rotation void rotate(int x) { int y = f[x]; int z = f[y]; int k = c[y][1] == x; // x is k-th child of y. int w = c[x][!k]; // the (1 - k)-th child of x. if(nroot(y)) c[z][c[z][1] == y] = x; c[x][!k] = y; c[y][k] = w; if(w) f[w] = y; f[y] = x; f[x] = z; update(y); // update(x) will be done after all rotate. } // splay x to be the root of its splay void splay(int x) { int y = x, z = 0; // push_rev the whole path from splay root to x. st[++z] = y; while(nroot(y)) st[++z] = y = f[y]; while(z) push_rev(st[z--]); while(nroot(x)) { y = f[x]; z = f[y]; if(nroot(y)) rotate((c[y][0] == x) ^ (c[z][0] == y) ? x : y); rotate(x); } update(x); } // make x to be in the same splay as root of real tree // and let x to have the largest weight in this splay, possibly discard right child in splay. void access(int x){ for(int y = 0; x; y = x, x = f[x]) { splay(x); // make x the root of its splay. c[x][1] = y; // make y (previous round's root) the right child of x. possibly discard the original right child. update(x); // update information // change x to be father to continue the process } } // change x to be the root of the real tree void makeroot(int x){ access(x); // make x in the same splay as root. splay(x); // make x the root of its splay. lazy_rev(x); // reverse the whole splay from x. This makes x the first node in the splay // Making x the root of the real tree doesn't change relative depth of other splay. // Tehrefore, reversing the splay from x effectively makes x the root of the real tree. } // find root in the real tree int findroot(int x) { access(x); // make x in the same splay as root. x has largest weight (depth in real tree) in its splay. splay(x); // make x the root of its splay. Thus, root of real tree will be left most node of this splay. while(c[x][0]) { // find leftmost node, which is root of real tree. push_rev(x); x = c[x][0]; } splay(x); // make root of real tree to be root of its splay again. return x; // return the root of real tree. } // create a splay with y being root and having largest weight, x smallest weight // thus, can query the path between x and y long long split(int x, int y) { makeroot(x); access(y); splay(y); return s[y]; } // connect x and y if x and y are not connect in the real tree // return whether an edge was cut bool link(int x, int y) { makeroot(x); if(findroot(y) == x) return false; f[x] = y; return true; } // cut x and y bool cut(int x, int y){ makeroot(x); if(findroot(y) == x && f[y] == x && !c[y][0]) { f[y] = c[x][1] = 0; update(x); return true; } return false; } void solve(int tt) { cout<<"Case #"<<tt<<": "; } int main(int argc, char * argv[]) { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // solve_testcase; int n,q; cin>>n>>q; for(int i=1;i<=n;++i) cin>>v[i]; long long inst,x,y; rep(i,0,n-1) { cin>>x>>y; x++; y++; // print(x,y); link(x, y); } rep(i,0,q) { cin>>inst; if(inst==0) { cin>>x>>y; x++; y++; cut(x,y); cin>>x>>y; x++; y++; link(x,y); } else if(inst==1) { cin>>x>>y; x++; splay(x); s[x] += y; v[x] += y; } else { cin>>x>>y; x++; y++; cout<<split(x, y)<<endl; } } return 0; }