Guest User

Untitled

a guest
Sep 5th, 2020
346
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #pragma GCC optimize("Ofast,unroll-loops")
  5. #pragma GCC target("avx,avx2,fma")
  6.  
  7. typedef long long LL;
  8. typedef pair<int, int> PII;
  9. typedef vector<int> VI;
  10. typedef long double db;
  11.  
  12. #define MP make_pair
  13. #define PB push_back
  14. #define X first
  15. #define Y second
  16.  
  17. #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
  18. #define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
  19. #define ALL(a) a.begin(), a.end()
  20. #define SZ(a) (int)((a).size())
  21. #define FILL(a, value) memset(a, value, sizeof(a))
  22. #define debug(a) cerr << #a << " = " << a << endl;
  23.  
  24. template<typename T> void setmax(T& x, T y) {x = max(x, y);}
  25. template<typename T> void setmin(T& x, T y) {x = min(x, y);}
  26.  
  27. template<typename T> void print(const T& a, ostream& out){
  28. for(auto i: a) out << i << ' ';
  29. out << endl;
  30. }
  31.  
  32. const double PI = acos(-1.0);
  33. const LL INF = 1e9 + 47;
  34. const LL LINF = INF * INF;
  35. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  36.  
  37. const int N = 50000 + 7;
  38. int n, q;
  39. int a[N];
  40. VI g[N];
  41. int tin[N], tout[N], timer;
  42. int sz[N];
  43. int parent[N];
  44. int w[N];
  45. int A[N];
  46.  
  47. void dfs_sz(int v, int p){
  48. parent[v] = p;
  49. sz[v] = 1;
  50. for(auto& i: g[v]) if (i == p){
  51. swap(i, g[v].back());
  52. g[v].pop_back();
  53. break;
  54. }
  55.  
  56. FOR(i, 0, SZ(g[v])){
  57. dfs_sz(g[v][i], v);
  58. sz[v] += sz[g[v][i]];
  59. if (sz[g[v][i]] > sz[g[v][0]]) swap(g[v][i], g[v][0]);
  60. }
  61. }
  62.  
  63. void dfs_order(int v, int p){
  64. tin[v] = timer++;
  65. if (SZ(g[v]) > 0){
  66. w[g[v][0]] = w[v];
  67. }
  68.  
  69. FOR(i, 0, SZ(g[v])){
  70. dfs_order(g[v][i], v);
  71. }
  72.  
  73. tout[v] = timer;
  74. }
  75.  
  76. inline int isAnc(int u, int v){
  77. return tin[u] <= tin[v] && tout[u] >= tout[v];
  78. }
  79.  
  80. inline void add_seg(int l, int r){
  81. FOR(i, l, r) a[i] ^= 1;
  82. }
  83.  
  84. inline void add(int u, int v){
  85. while(!isAnc(w[u], v)){
  86. add_seg(tin[w[u]], tin[u] + 1);
  87. u = parent[w[u]];
  88. }
  89.  
  90. while(w[u] != w[v]){
  91. add_seg(tin[w[v]], tin[v] + 1);
  92. v = parent[w[v]];
  93. }
  94. add_seg(min(tin[u], tin[v]), max(tin[u], tin[v]) + 1);
  95. }
  96.  
  97. vector<int> vec[N];
  98. const int magic = 1000;
  99. int Id[N];
  100. int ptr = 0;
  101.  
  102. inline LL solve(int v){
  103. LL ans = 0;
  104. int all = 0, C = 0;
  105. all = a[tin[v]];
  106.  
  107. if (SZ(g[v]) <= magic){
  108. for(auto i: g[v]){
  109. const int L = tin[i], R = tout[i];
  110. FOR(j, L, R) C += a[j];
  111. ans += all * (LL) C;
  112. all += C;
  113. C = 0;
  114. }
  115. }else{
  116. const int L = tin[v] + 1, R = tout[v];
  117.  
  118. const auto& is = vec[Id[v]];
  119. FOR(i, L, R){
  120. if (is[i]){
  121. ans += all * (LL) C;
  122. all += C;
  123. C = 0;
  124. }
  125.  
  126. C += a[i];
  127. }
  128. }
  129.  
  130. ans += all * (LL) C;
  131. return ans;
  132. }
  133.  
  134. int main()
  135. {
  136. ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  137.  
  138. cin >> n >> q;
  139. FOR(i, 0, n) cin >> a[i];
  140. FOR(i, 1, n){
  141. int u, v;
  142. cin >> u >> v;
  143. --u; --v;
  144. g[u].PB(v);
  145. g[v].PB(u);
  146. }
  147.  
  148. dfs_sz(0, 0);
  149. iota(w, w + n, 0);
  150. dfs_order(0, 0);
  151. FOR(i, 0, n) A[tin[i]] = a[i];
  152. FOR(i, 0, n) a[i] = A[i];
  153.  
  154. FOR(i, 0, n) if (SZ(g[i]) > magic){
  155. vector<int>& v = vec[ptr];
  156. v.assign(n, 0);
  157. for(auto j: g[i]) v[tin[j]] = true;
  158. Id[i] = ptr;
  159. ptr++;
  160. }
  161.  
  162. while(q--){
  163. int typ, x;
  164. cin >> typ >> x;
  165. --x;
  166. if (typ == 1){
  167. add(0, x);
  168. }else{
  169. if (SZ(g[x]) == 0){
  170. cout << "0\n";
  171. continue;
  172. }
  173.  
  174.  
  175. cout << solve(x) << '\n';
  176. }
  177. }
  178.  
  179. return 0;
  180. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×