fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define IOS  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  5. #define ll               long long
  6. #define pb               push_back
  7. #define vll              vector<ll>
  8. #define pll              pair<ll,ll>
  9. #define vpll             vector<pll>
  10. #define all(v) v.begin(),v.end()
  11.  
  12.  
  13. const int N = 1e5+7;
  14. ll time_in = 0; ll idx = 0; ll n,m,q; 
  15. vll value(N),color(N),left_range_(N),right_range_(N),parent(N,0),depth(N,0),subtree_size(N,0),heavy(N,0);   
  16. vll head(N,0),lt(N,0),pos(N,0),pos_out(N,0);
  17.  
  18. void dfs(int node,int par,vll adj[],int dep){
  19.     parent[node] = par;
  20.     depth[node] = dep;
  21.     for(auto x: adj[node]){
  22.         if(x != par){
  23.             dfs(x,node,adj,dep+1);
  24.             subtree_size[node] += subtree_size[x]; 
  25.             if(subtree_size[x] >  subtree_size[heavy[node]]){
  26.                 heavy[node] = x;
  27.             }
  28.         }
  29.     }
  30.     subtree_size[node]++;
  31. } 
  32.  
  33. ll lca(ll x,ll y){   
  34.         while(head[x] != head[y]){
  35.             if(depth[head[x]] < depth[head[y]]) swap(x,y);
  36.             x = parent[head[x]];
  37.         }
  38.         if(depth[x] < depth[y]) swap(x,y);
  39.     return y;
  40. }
  41. void dfsHLD(int node,vll adj[], ll chain){
  42.     head[node] = chain;
  43.     lt[idx] = value[node];
  44.     pos[node] = idx++;
  45.     if(heavy[node] != 0){
  46.         dfsHLD(heavy[node],adj,chain);
  47.     }
  48.     for(auto x: adj[node]){
  49.         if(x != parent[node] and x != heavy[node]){
  50.                 dfsHLD(x,adj,x);
  51.         }
  52.     } 
  53.     pos_out[node] = idx;
  54. }
  55.  
  56.  
  57.  
  58. vpll arr;
  59. vll lazyarr;
  60.  
  61. void merge(ll ind, ll left, ll right)
  62. {
  63.     arr[ind]=arr[left];
  64.     arr[ind].first+=arr[right].first;
  65.     arr[ind].second+=arr[right].second;
  66. }
  67.  
  68. void update_lazy(ll ind, ll lo, ll hi)
  69. {
  70.     if (lazyarr[ind]==0) return;
  71.     ll upd=lazyarr[ind];
  72.     lazyarr[ind]=0;
  73.     if (upd==1)
  74.         arr[ind].first+=arr[ind].second, arr[ind].second=0;
  75.     else
  76.         arr[ind].second+=arr[ind].first, arr[ind].first=0;
  77.     if (lo!=hi)
  78.         lazyarr[2*ind+1]=upd, lazyarr[2*ind+2]=upd;
  79. }
  80.  
  81. void build(ll ind, ll lo, ll hi, vll &v)
  82. {
  83.     if (lo==hi)
  84.     {
  85.         if (v[lo]>=0) arr[ind].first=v[lo], arr[ind].second=0;
  86.         else arr[ind].first=0, arr[ind].second=-v[lo];
  87.         return;
  88.     }
  89.     ll mid=(hi+lo)/2;
  90.     build(2*ind+1,lo,mid,v);
  91.     build(2*ind+2,mid+1,hi,v);
  92.     merge(ind,2*ind+1,2*ind+2);
  93. }
  94.  
  95. void update(ll ind, ll lo, ll hi, ll l, ll r, ll d)
  96. {
  97.     // check for update
  98.     update_lazy(ind,lo,hi);
  99.     if (lo>r || hi<l) return;
  100.     else if (lo>=l && hi<=r)
  101.     {
  102.         if (d==1)
  103.             arr[ind].first+=arr[ind].second, arr[ind].second=0;
  104.         else
  105.             arr[ind].second+=arr[ind].first, arr[ind].first=0;
  106.         if (lo!=hi)
  107.             lazyarr[2*ind+1]=d, lazyarr[2*ind+2]=d;
  108.     }
  109.     else
  110.     {
  111.         ll mid=(hi+lo)/2;
  112.         update(2*ind+1,lo,mid,l,r,d);
  113.         update(2*ind+2,mid+1,hi,l,r,d);
  114.         merge(ind,2*ind+1,2*ind+2);
  115.     }
  116. }
  117.  
  118. ll query(ll ind, ll lo, ll hi, ll l, ll r)
  119. {
  120.     // check for update
  121.     update_lazy(ind,lo,hi);
  122.     if (lo>r || hi<l) return 0;
  123.     else if (lo>=l && hi<=r) return arr[ind].first-arr[ind].second;
  124.     ll mid=(hi+lo)/2;
  125.     ll left=query(2*ind+1,lo,mid,l,r);
  126.     ll right=query(2*ind+2,mid+1,hi,l,r);
  127.     ll ans=left+right;
  128.     return ans;
  129. }
  130.  
  131. vpll brr;  // { count 0, count 1}
  132. vll lazy;
  133. // 0 -> no update_color
  134. // 1 -> force 0
  135. // 2 -> force 1
  136.  
  137. void merge_color(ll ind, ll left, ll right)
  138. {
  139.     brr[ind]=brr[left];
  140.     brr[ind].first+=brr[right].first;
  141.     brr[ind].second+=brr[right].second;
  142. }
  143.  
  144. void update_lazy_color(ll ind, ll lo, ll hi)
  145. {
  146.     if (lazy[ind]==0) return;
  147.     ll elem=hi-lo+1;
  148.     ll upd=lazy[ind];
  149.     if (lazy[ind]==1) brr[ind]={elem,0};
  150.     else brr[ind]={0,elem};
  151.     lazy[ind]=0;
  152.     if (lo!=hi) lazy[2*ind+1]=upd, lazy[2*ind+2]=upd;
  153. }
  154.  
  155. void build_color(ll ind, ll lo, ll hi, vll &v)
  156. {
  157.     if (lo==hi)
  158.     {
  159.         if (v[lo]==0) brr[ind]={1,0};
  160.         else brr[ind]={0,1};
  161.         return;
  162.     }
  163.     ll mid=(hi+lo)/2;
  164.     build_color(2*ind+1,lo,mid,v);
  165.     build_color(2*ind+2,mid+1,hi,v);
  166.     merge_color(ind,2*ind+1,2*ind+2);
  167. }
  168.  
  169. void update_color(ll ind, ll lo, ll hi, ll l, ll r, ll x)
  170. {
  171.     // check update_color in lazy
  172.     update_lazy_color(ind,lo,hi);
  173.     if (lo>r || hi<l) return;
  174.     else if (lo>=l && hi<=r)
  175.     {
  176.         ll elem=hi-lo+1;
  177.         if (x==1) brr[ind]={elem,0};
  178.         else brr[ind]={0,elem};
  179.         if (lo!=hi) lazy[2*ind+1]=x, lazy[2*ind+2]=x;
  180.     }
  181.     else
  182.     {
  183.         ll mid=(hi+lo)/2;
  184.         update_color(2*ind+1,lo,mid,l,r,x);
  185.         update_color(2*ind+2,mid+1,hi,l,r,x);
  186.         merge_color(ind,2*ind+1,2*ind+2);
  187.     }
  188. }
  189.  
  190. ll query_color(ll ind, ll lo, ll hi, ll l, ll r)
  191. {
  192.     // check update_color in lazy
  193.     update_lazy_color(ind,lo,hi);
  194.     if (lo>r || hi<l) return 0;
  195.     else if (lo>=l && hi<=r) return brr[ind].second;
  196.     ll mid=(hi+lo)/2;
  197.     ll left=query_color(2*ind+1,lo,mid,l,r);
  198.     ll right=query_color(2*ind+2,mid+1,hi,l,r);
  199.     ll ans=left+right;
  200.     return ans;
  201. }
  202.  
  203.  
  204. ll get_the_value_color(int x,int y){
  205.     ll sum = 0;
  206.     while(head[x] != head[y]){
  207.         if(depth[head[x]] < depth[head[y]]) swap(x,y);
  208.         ll value = query_color(0,0,n-1,pos[head[x]], pos[x]);
  209.         sum += value;
  210.         x = parent[head[x]];
  211.     }    
  212.     if(depth[x] < depth[y]) swap(x,y);
  213.     ll value = query_color(0,0,n-1,pos[y],pos[x]);
  214.     if(pos[x] >= pos[y]) sum += value;
  215.     return sum;
  216. }
  217.  
  218.  
  219. void update_the_color(int x,int y,int color){
  220.     while(head[x] != head[y]){
  221.         if(depth[head[x]] < depth[head[y]]) swap(x,y);
  222.         update_color(0,0,n-1,pos[head[x]],pos[x],color);
  223.         x = parent[head[x]];
  224.     }    
  225.     if(depth[x] < depth[y]) swap(x,y);
  226.     if(pos[x] >= pos[y] )update_color(0,0,n-1,pos[y],pos[x],color);
  227. }
  228.  
  229. void update_the_value(int x,int y,int sign){
  230.     while(head[x] != head[y]){
  231.         if(depth[head[x]] < depth[head[y]]) swap(x,y);
  232.         update(0,0,n-1,pos[head[x]],pos[x],sign);
  233.         x = parent[head[x]];
  234.     }    
  235.     if(depth[x] < depth[y]) swap(x,y);
  236.     if(pos[x] >= pos[y] )update(0,0,n-1,pos[y],pos[x],sign);
  237. }
  238.  
  239.  
  240. ll get_the_value(int x,int y){
  241.      ll sum = 0;
  242.     while(head[x] != head[y]){
  243.         if(depth[head[x]] < depth[head[y]]) swap(x,y);
  244.         ll value =  query(0,0,n-1,pos[head[x]],pos[x]);
  245.         sum += value;
  246.         x = parent[head[x]];
  247.     }    
  248.     if(depth[x] < depth[y]) swap(x,y);
  249.     ll value = query(0,0,n-1,pos[y],pos[x]);
  250.     if(pos[x] >= pos[y]) sum += value;
  251.     return sum;
  252. }
  253.  
  254. template<typename Node, typename Update>
  255. struct SegTree {
  256.     vector<Node> tree;
  257.     vector<ll> arr; // type may change
  258.     int n;
  259.     int s;
  260.     SegTree(int a_len, vector<ll> &a) { // change if type updated
  261.         arr = a;
  262.         n = a_len;
  263.         s = 1;
  264.         while(s < 2 * n){
  265.             s = s << 1;
  266.         }
  267.         tree.resize(s); fill(all(tree), Node());
  268.         build(0, n - 1, 1);
  269.     }
  270.     void build(int start, int end, int index)  // Never change this
  271.     {
  272.         if (start == end)   {
  273.             tree[index] = Node(arr[start]);
  274.             return;
  275.         }
  276.         int mid = (start + end) / 2;
  277.         build(start, mid, 2 * index);
  278.         build(mid + 1, end, 2 * index + 1);
  279.         tree[index].merge(tree[2 * index], tree[2 * index + 1]);
  280.     }
  281.     void update(int start, int end, int index, int query_index, Update &u)  // Never Change this
  282.     {
  283.         if (start == end) {
  284.             u.apply(tree[index]);
  285.             return;
  286.         }
  287.         int mid = (start + end) / 2;
  288.         if (mid >= query_index)
  289.             update(start, mid, 2 * index, query_index, u);
  290.         else
  291.             update(mid + 1, end, 2 * index + 1, query_index, u);
  292.         tree[index].merge(tree[2 * index], tree[2 * index + 1]);
  293.     }
  294.     Node query(int start, int end, int index, int left, int right) { // Never change this
  295.         if (start > right || end < left)
  296.             return Node();
  297.         if (start >= left && end <= right)
  298.             return tree[index];
  299.         int mid = (start + end) / 2;
  300.         Node l, r, ans;
  301.         l = query(start, mid, 2 * index, left, right);
  302.         r = query(mid + 1, end, 2 * index + 1, left, right);
  303.         ans.merge(l, r);
  304.         return ans;
  305.     }
  306.     void make_update(int index, ll val) {  // pass in as many parameters as required
  307.         Update new_update = Update(val); // may change
  308.         update(0, n - 1, 1, index, new_update);
  309.     }
  310.     Node make_query(int left, int right) {
  311.         return query(0, n - 1, 1, left, right);
  312.     }
  313. };
  314.  
  315. // all positive
  316.  
  317.  
  318. struct Node1 {
  319.     ll val; // may change
  320.     Node1() { // Identity element
  321.         val = 0;    // may change
  322.     }
  323.     Node1(ll p1) {  // Actual Node
  324.         val = p1; // may change
  325.     }
  326.     void merge(Node1 &l, Node1 &r) { // Merge two child nodes
  327.         val = l.val + r.val;  // may change
  328.     }
  329. };
  330.  
  331. struct Update1 {
  332.     ll val; // may change
  333.     Update1(ll p1) { // Actual Update
  334.         val = p1; // may change
  335.     }
  336.     void apply(Node1 &a) { // apply update to given node
  337.         a.val = val; // may change
  338.     }
  339. };
  340.  
  341.  
  342. void solve() {
  343.    cin>>n>>q;
  344.     assert(n >= 1 and n <= 100000);
  345.     assert(q >= 1 and q <= 100000);
  346.     color.resize(n + 1); value.resize(n + 1); 
  347.     for(int i = 0; i< n; i++) color[i] = 0;
  348.     arr.clear(); lazyarr.clear(); arr.resize(4*n+1); lazyarr.resize(4*n+1,0);
  349.     brr.clear(); lazy.clear(); brr.resize(4*n+1); lazy.resize(4*n+1,0);
  350.     vector<ll> adj[n + 1];
  351.     for(int i = 0; i< n-1; i++){
  352.         ll x,y; cin>>x>>y;
  353.         assert(x >= 1 and x <= n); assert(y >= 1 and y <= n);
  354.         adj[x].push_back(y);
  355.         adj[y].pb(x);
  356.     }
  357.     for(int i = 1; i<= n; i++) cin>>value[i];
  358.     parent.resize(n + 1);  depth.resize(n + 1); subtree_size.resize(n + 1); heavy.resize(n + 1); head.resize(n + 1);
  359.     lt.resize(n + 1); pos.resize(n + 1); pos_out.resize(n + 1); 
  360.     dfs(1,0,adj,0); // main dfs calling
  361.     dfsHLD(1,adj,1); // hld dfs calling
  362.     auto lt1 = lt; // decomposed array after HLD
  363.     build(0,0,n-1,lt); // segment tree for the mix of black and white node values
  364.     build_color(0,0,n-1,color); // segment tree for saving the color white and black nodes
  365.     SegTree<Node1,Update1> sg = SegTree<Node1,Update1> (n,lt1); // segment tree storing all the original values
  366.     //all nodes are considered positive means all nodes are black first
  367.     update(0,0,n-1,0,n-1,-1); // coloring all the node white first
  368.     for(int i = 0; i < q; i++){
  369.         int qType; cin>>qType;
  370.         assert(qType >= 1 and qType <= 3);
  371.         if(qType == 1){
  372.             ll x,y ;cin>>x>>y;
  373.             assert(x >= 1 and x <= n);
  374.             assert(y >= 1 and y <= n);
  375.             ll lca_node = lca(x,y);
  376.             ll path_dist = abs(depth[lca_node] - depth[x]) + abs(depth[lca_node] - depth[y]) + 1;
  377.             ll black_nodes = get_the_value_color(x,y);
  378.             ll white_nodes = path_dist - black_nodes;
  379.             if(black_nodes > white_nodes){
  380.                 update_the_color(x,y,2);
  381.                 update_the_value(x,y,1);
  382.             }else if(black_nodes < white_nodes){
  383.                 update_the_color(x,y,1);
  384.                 update_the_value(x,y,-1);
  385.             }
  386.         }else if(qType == 2){
  387.                 ll x; cin>>x;
  388.                 assert(x >= 1 and x <= n);
  389.                 update_color(0,0,n-1,pos[x], pos_out[x] - 1,2); // changing the color of the subtree
  390.                 update(0,0,n-1,pos[x], pos_out[x] - 1,1); // change the subtree with positive values means black nodes
  391.         }else{
  392.                 ll a,b ;cin>>a>>b;
  393.                 assert(a >= 1 and a <= n);
  394.                 assert(b >= 1 and b <= n);
  395.                 ll x,y; x = a; y = b;
  396.                 ll total_value = 0;
  397.                 while(head[x] != head[y]){
  398.                     if(depth[head[x]] < depth[head[y]]) swap(x,y);
  399.                     total_value += sg.make_query(pos[head[x]],pos[x]).val;
  400.                     x = parent[head[x]];
  401.                 }    
  402.                 if(depth[x] < depth[y]) swap(x,y);
  403.                 if(pos[x] >= pos[y]) total_value += sg.make_query(pos[y],pos[x]).val;
  404.                 // total_value --> getting the original values considered all nodes are black
  405.                 ll path_value = get_the_value(a,b); // getting the values where both positive and negative values are there
  406.                 ll black_value = (total_value + path_value) / 2;
  407.                 ll white_value = (total_value - path_value) / 2;
  408.                 cout<<max(white_value,black_value)<<endl;
  409.         }        
  410.     }
  411. }
  412.  
  413. int main()
  414.  {
  415.      IOS;
  416.  
  417.  #ifndef ONLINE_JUDGE
  418.      freopen("error.txt", "w", stderr);
  419.  #endif
  420.      int test = 1;
  421.      // cin >> test;
  422.      for (int i = 1; i <= test; i++) {
  423.          // cout << "Case " << i << ": "<<endl;
  424.         solve();
  425.      }
  426.      return 0;
  427.  }
  428.  
Runtime error #stdin #stdout #stderr 0.01s 12912KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:344: void solve(): Assertion `n >= 1 and n <= 100000' failed.
https://ideone.com/M3j7k6
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!