Submit Info #29230

Problem Lang User Status Time Memory
Dynamic Tree Subtree Add Subtree Sum cpp misir AC 550 ms 16.92 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
max_random_00 AC 524 ms 16.84 MiB
max_random_01 AC 550 ms 16.87 MiB
max_random_02 AC 510 ms 16.85 MiB
max_random_03 AC 505 ms 16.92 MiB
max_random_04 AC 502 ms 16.85 MiB
random_00 AC 340 ms 11.11 MiB
random_01 AC 362 ms 12.91 MiB
random_02 AC 220 ms 5.27 MiB
random_03 AC 144 ms 13.46 MiB
random_04 AC 153 ms 2.20 MiB
small_00 AC 1 ms 0.64 MiB
small_01 AC 1 ms 0.60 MiB
small_02 AC 1 ms 0.64 MiB
small_03 AC 1 ms 0.60 MiB
small_04 AC 2 ms 0.64 MiB

/*بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم*/ //#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx,avx2,fma") #include <bits/stdc++.h> using namespace std; #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); typedef long long ll; using pii = pair<int, int>; const double PI = acos(-1.0); const ll mod = 1e9 + 7; //const ll mod = 998244353; inline void normal(ll &a) { a %= mod; (a < 0) && (a += mod); } inline ll modMul(ll a, ll b) { a %= mod, b %= mod; normal(a), normal(b); return (a * b) % mod; } inline ll modAdd(ll a, ll b) { a %= mod, b %= mod; normal(a), normal(b); return (a + b) % mod; } inline ll modSub(ll a, ll b) { a %= mod, b %= mod; normal(a), normal(b); a -= b; normal(a); return a; } inline ll modPow(ll b, ll p) { ll r = 1; while (p) { if (p & 1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; } inline ll modInverse(ll a) { return modPow(a, mod - 2); } inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); } #define si(x) scanf("%d",&x) #define sii(x,y) scanf("%d %d",&x,&y) #define siii(x,y,z) scanf("%d %d %d",&x,&y,&z) #define sl(x) scanf("%lld",&x) #define sll(x,y) scanf("%lld %lld",&x,&y) #define slll(x,y,z) scanf("%lld %lld %lld",&x,&y,&z) #define ss(ch) scanf("%s",ch) #define pi(x) printf("%d",x) #define pii(x,y) printf("%d %d",x,y) #define piii(x,y,z) printf("%d %d %d",x,y,z) #define pl(x) printf("%lld",x) #define pll(x,y) printf("%lld %lld",x,y) #define plll(x,y,z) printf("%lld %lld %lld",x,y,z) #define ps(ch) printf("%s",ch) #define F(i,a,b) for(int i= a; i <= b; i++) #define R(i,b,a) for(int i= b; i >= a; i--) #define REP(i,n) for(int i = 0; i < (n); i++) int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1}; int dy8[] = {1, -1, -1, 0, 1, -1, 0, 1}; int kx8[] = {1, 1, 2, 2, -1, -1, -2, -2}; int ky8[] = {2, -2, 1, -1, 2, -2, 1, -1}; /* for Random Number generate mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); */ ///** template < typename F, typename S >ostream& operator << ( ostream& os, const pair< F, S > & p ) {return os << "(" << p.first << ", " << p.second << ")";} template < typename T >ostream &operator << ( ostream & os, const vector< T > &v ) {os << "{"; for (auto it = v.begin(); it != v.end(); ++it) {if ( it != v.begin() ) os << ", "; os << *it;} return os << "}";} template < typename T >ostream &operator << ( ostream & os, const set< T > &v ) {os << "["; for (auto it = v.begin(); it != v.end(); ++it) {if ( it != v.begin()) os << ", "; os << *it;} return os << "]";} template < typename F, typename S >ostream &operator << ( ostream & os, const map< F, S > &v ) {os << "["; for (auto it = v.begin(); it != v.end(); ++it) {if ( it != v.begin() ) os << ", "; os << it -> first << " = " << it -> second ;} return os << "]";} #define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0) clock_t tStart = clock(); #define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC) void faltu () { cerr << endl; } template <typename T>void faltu( T a[], int n ) {for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl;} template <typename T, typename ... hello> void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); } // Program showing a policy-based data structure. #include <ext/pb_ds/assoc_container.hpp> // Common file #include <ext/pb_ds/tree_policy.hpp> #include <functional> // for less using namespace __gnu_pbds; // GNU link : https://goo.gl/WVDL6g typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> new_data_set; // find_by_order(k) – ফাংশনটি kth ordered element এর একটা পয়েন্টার রিটার্ন করে। অর্থাৎ তুমি চাইলেই kth ইন্ডেক্সে কি আছে, সেটা জেনে ফেলতে পারছো! // order_of_key(x) – ফাংশনটি x এলিমেন্টটা কোন পজিশনে আছে সেটা বলে দেয়। //*//**___________________________________________________**/ int ri() { int n; scanf("%d", &n); return n; } struct Node; extern Node *NONE; struct Node { #define l ch[0] #define r ch[1] Node *ch[2] = {NONE, NONE}; Node *p = NONE; int64_t val = 0; int64_t sum = 0; int64_t added = 0; int64_t cancel = 0; int size = 0; int64_t light_sum = 0; // LIGHT int light_size = 0; // LIGHT bool rev = false; void fetch() { if (l != NONE) l->flush(); if (r != NONE) r->flush(); sum = val + l->sum + r->sum + light_sum; size = 1 + l->size + r->size + light_size; } void add(int64_t add_val) { val += add_val; sum += add_val * size; added += add_val; light_sum += add_val * light_size; } void flush() { if (p != NONE) { add(p->added - cancel); cancel = p->added; } if (rev) { std::swap(l, r); l->rev ^= 1; r->rev ^= 1; rev = false; } } void rotate(int dir) { Node *new_root = ch[!dir]; assert(new_root != NONE); if (new_root->ch[dir] != NONE) new_root->ch[dir]->flush(); ch[!dir] = new_root->ch[dir]; ch[!dir]->p = this; ch[!dir]->cancel = added; new_root->ch[dir] = this; if (p->l == this) p->l = new_root; if (p->r == this) p->r = new_root; new_root->p = p; new_root->cancel = p->added; p = new_root; cancel = new_root->added; fetch(), new_root->fetch(); } bool is_root() { return p == NONE || (p->l != this && p->r != this); } void splay() { while (!is_root()) { if (p->is_root()) { p->flush(), flush(); p->rotate(p->l == this); } else { Node *pp = p->p; pp->flush(), p->flush(), flush(); bool flag0 = pp->l == p; bool flag1 = p->l == this; if (flag0 == flag1) pp->rotate(flag0); p->rotate(flag1); if (flag0 != flag1) pp->rotate(flag0); } } flush(); } Node *expose() { Node *prev = NONE; for (Node *cur = this; cur != NONE; cur = cur->p) { cur->splay(); if (cur->r != NONE) { // add cur->r->flush(); cur->light_size += cur->r->size; cur->light_sum += cur->r->sum; } cur->r = prev; if (cur->r != NONE) { // remove cur->r->flush(); cur->light_size -= cur->r->size; cur->light_sum -= cur->r->sum; } cur->fetch(); prev = cur; } splay(); return prev; } void link(Node *parent) { parent->expose(); expose(); p = parent; cancel = parent->added; p->r = this; p->fetch(); } void cut() { expose(); l->flush(); l->p = NONE; l = NONE; fetch(); } void evert() { expose(); rev ^= 1; flush(); } #undef l #undef r }; Node *NONE = new Node; template<class T> std::vector<std::pair<int, int> > random_tree(int n, T &rnd) { std::vector<std::pair<int, int> > res; for (int i = 1; i < n; i++) res.push_back({std::uniform_int_distribution<>(0, i - 1)(rnd), i}); int perm[n]; std::iota(perm, perm + n, 0); std::shuffle(perm, perm + n, rnd); for (auto &i : res) { if (std::uniform_int_distribution<>(0, 1)(rnd)) std::swap(i.first, i.second); i.first = perm[i.first]; i.second = perm[i.second]; } return res; } struct Fast { std::vector<Node> nodes; Fast (const std::vector<std::pair<int, int> > &hens) { int n = hens.size() + 1; nodes.resize(n); for (auto &i : nodes) i.fetch(); for (auto i : hens) { nodes[i.first].evert(); nodes[i.first].link(&nodes[i.second]); } } void add(int v, int p) { nodes[p].evert(); nodes[v].cut(); nodes[v].add(1); nodes[v].link(&nodes[p]); } int sum(int v, int p) { nodes[p].evert(); nodes[v].cut(); int res = nodes[v].sum; nodes[v].link(&nodes[p]); return res; } }; struct Gu { std::vector<std::vector<int> > hen; std::vector<int> val; Gu (const std::vector<std::pair<int, int> > &hens) { int n = hens.size() + 1; hen.resize(n); for (auto i : hens) { hen[i.first].push_back(i.second); hen[i.second].push_back(i.first); } val.resize(n); } void add(int i, int p) { val[i]++; for (auto j : hen[i]) if (j != p) add(j, i); } int sum(int i, int p) { int res = val[i]; for (auto j : hen[i]) if (j != p) res += sum(j, i); return res; } }; std::random_device rnd_dev; std::mt19937 rnd(rnd_dev() ^ time(NULL)); bool random_check(int n, int q) { auto tree = random_tree(n, rnd); struct Query { int type; int v; int p; }; std::vector<int> hen[n]; for (auto i : tree) hen[i.first].push_back(i.second), hen[i.second].push_back(i.first); std::vector<Query> qs; for (int i = 0; i < q; i++) { int t = std::uniform_int_distribution<>(1, 2)(rnd); int v = std::uniform_int_distribution<>(0, n - 1)(rnd); int p = hen[v][std::uniform_int_distribution<>(0, hen[v].size() - 1)(rnd)]; qs.push_back({t, v, p}); } Gu gu(tree); Fast fast(tree); for (int i = 0; i < q; i++) { if (qs[i].type == 1) { gu.add(qs[i].v, qs[i].p); fast.add(qs[i].v, qs[i].p); } else { int r0 = gu.sum(qs[i].v, qs[i].p); int r1 = fast.sum(qs[i].v, qs[i].p); if (r0 != r1) { std::cerr << "!!! FAILED !!! at query #" << i << std::endl; std::cerr << "correct:" << r0 << " wrong:" << r1 << std::endl; std::cerr << n << " " << q << std::endl; for (auto i : tree) std::cerr << i.first << " " << i.second << std::endl; for (auto i : qs) std::cerr << i.type << " " << i.v << " " << i.p << std::endl; return false; } } } return true; } //Code Courtesy: QCFium int main() { /* #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); freopen("error.txt", "w", stderr); #endif //*/ int n = ri(); int q = ri(); Node nodes[n]; for (auto &i : nodes) i.val = ri(), i.fetch(); for (int i = 1; i < n; i++) { int a = ri(); int b = ri(); nodes[a].evert(); nodes[a].link(nodes + b); } // auto to_str = [&] (Node * node) -> std::string { // if (node == NONE) return "NONE"; // else return "#" + std::to_string(node - nodes); // }; // auto debug = [&] (Node & node) { // std::cerr << to_str(&node) << " p:" << to_str(node.p) << " [" << to_str(node.ch[0]) << "," << to_str(node.ch[1]) << "] rev:" << node.rev << std::endl; // std::cerr << " val:" << node.val << " sum:" << node.sum << " added:" << node.added << " cancel:" << node.cancel << " lsum:" << node.light_sum << " lsize:" << node.light_size << " size:" << node.size << std::endl; // }; for (int i = 0; i < q; i++) { int t = ri(); if (t == 0) { int r0 = ri(); int r1 = ri(); nodes[r0].evert(); nodes[r1].cut(); r0 = ri(); r1 = ri(); nodes[r0].evert(); nodes[r0].link(nodes + r1); } else { int v = ri(); int p = ri(); nodes[p].evert(); nodes[v].cut(); if (t == 1) nodes[v].add(ri()); else printf("%" PRId64 "\n", nodes[v].sum); nodes[v].link(nodes + p); } } return 0; }