AASHRAM - Editorial

PROBLEM LINK:

Practice

Contest

Author: syntaxerorr

Tester: spaesk

Editorialist: syntaxerorr

Difficulty:

Medium

Prerequisites:

Euler tour, segment tree, lazy propagation

Problem:

You are given a tree with ‘N’ nodes rooted at node 1 with each node ‘u’ associated with weight a[u] . You are also given 2 type of queries to perform on the tree. The number of queries is ‘M’.

  1. 1 U VAL : For query of type 1 you will be given a node ‘U’ and an integer VAL. let sum of subtree = (sum of weights of all nodes in the subtree of ‘U’ including ‘U’). If the sum of subtree of node ‘U’ is even then add VAL to every node of the subtree of ‘U’ (including node ‘U’) else add 1 to every node of the subtree (including node ‘U’).

  2. 2 U V: For query of type 2 you will be given two nodes ‘U’ and ‘V’ and you have to print the bitwise XOR of the subtree sum of ‘U’ and ‘V’.

Explanation:

First perform Euler tour on the tree to flatten the tree into a vector and store the starting and ending indexes of the subtree of some node ‘v’ while performing the euler tour. For example if tree is:

Then the flattened tree is : 1 3 2 5 4

with,

start [1] = 0 , end [1] = 4

start [2] = 2 , end [2] = 2

start [3] = 1 , end [3] = 2

start [4] = 4 , end [4] = 4

start [5] = 3 , end [5] = 4

( follow 0 – based indexing)

Now, we form a segment tree with lazy propagation ( for range updates of whole subtree ) from the flattened tree with range of each node in the segment tree being start[v] , end [v] for some node v. The segment tree formed from sample input is:

For query of type 1,

We first check if the current sum of subtree of node ‘U’ is odd or even. If it is even then we update the range with val else we update it with 1.

For query of type 2,

We process 2 queries for node ‘U’ and ‘V’ and print the bitwise xor of the values returned by the query function.

Time Complexity:

Time complexity for segment tree construction : O(N)

Time complexity of update and query operation : O(log(N))

Overall time complexity: O(N + M*log(N) )

Setter’s solution:

#include<bits/stdc++.h>

#include<fstream>

using namespace std;#
define fio ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#define lli long long int
#define f(i, a, b) for (i = a; i < b; i++)
#define r(i, a) for (i = a; i >= 0; i--)
#define fr(i, a, b) for (i = a; i >= b; i--)
#define ff first# define sc second# define mp make_pair
#define pb push_back# define nl cout << endl
#define full(v) v.begin(), v.end()
#define ms(a) memset(a, 0, sizeof(a))
#define sz(a) a.size()
#define llu unsigned long long int
#define pi pair < int, int > 
#define plli pair < lli, lli > 
#define ppl pair < lli, pair < lli, lli > > 
#define ppi pair < int, pair < int, int > > 
#define vlli vector < lli > v;
#define vii vector < int > v;
#define vl(n) vector < lli > v[n];
#define fu fflush(stdout)
#define in (a, n) lli a[n];for (lli i = 0; i < n; i++) cin >> a[i];
#define pv(v) for (auto it = v.begin(), v.end(), it++) cout << * it << " ";
#define ps(s) for (auto it = s.begin(); it != s.end(); it++) cout << * it << " ";
#define mod 1000000007
#define mod2 998244353
#define msb(b) memset(b, true, sizeof(b))
#define msf(b) memset(b, false, sizeof(b))
#define MAXN 100005lli st[MAXN], ed[MAXN], lazy[4 * MAXN], seg[4 * MAXN];

vector < lli > tree; // stores the flattened tree

// curr is current node , par is parent of curr
void et(vector < lli > vc[], int curr, int par) {
  st[curr] = tree.size(); // store the starting index of subtree of node curr

  tree.pb(curr); // insert node curr in vector tree

  for (auto it = vc[curr].begin(); it != vc[curr].end(); it++)
    if ( * it != par)
      et(vc, * it, curr);
  ed[curr] = tree.size() - 1; // store the ending index of subtree of node curr
}

// ss is starting index and se is ending index of segment/range
void build(lli a[], int ss, int se, int idx) {
  if (ss == se) {
    // a[tree[ss]] represents the value of node present at tree[ss]
    seg[idx] = a[tree[ss]];
    return;
  }
  int mid = (ss + se) / 2;
  build(a, ss, mid, 2 * idx + 1);
  build(a, mid + 1, se, 2 * idx + 2);
  seg[idx] = seg[2 * idx + 1] + seg[2 * idx + 2];
}

void update(int ss, int se, int qs, int qe, int idx, lli val) {

  if (lazy[idx] != 0) {
    seg[idx] += (se - ss + 1) * lazy[idx];
    if (ss != se) {
      lazy[2 * idx + 1] += lazy[idx];
      lazy[2 * idx + 2] += lazy[idx];
    }
    lazy[idx] = 0;
  }

  if (qe < ss || qs > se)
    return;

  if (qs <= ss && se <= qe) {
    seg[idx] += (se - ss + 1) * val;
    if (ss != se) {
      lazy[2 * idx + 1] += val;
      lazy[2 * idx + 2] += val;
    }
  } else if (ss != se) {
    int mid = (ss + se) / 2;
    update(ss, mid, qs, qe, 2 * idx + 1, val);
    update(mid + 1, se, qs, qe, 2 * idx + 2, val);
    seg[idx] = seg[2 * idx + 1] + seg[2 * idx + 2];
  }
}

lli query(int ss, int se, int qs, int qe, int idx) {
  if (lazy[idx] != 0) {
    seg[idx] += (se - ss + 1) * lazy[idx];
    if (ss != se) {
      lazy[2 * idx + 1] += lazy[idx];
      lazy[2 * idx + 2] += lazy[idx];
    }
    lazy[idx] = 0;
  }

  if (qe < ss || qs > se)
    return 0;

  if (qs <= ss && se <= qe)
    return seg[idx];

  int mid = (ss + se) / 2;
  return query(ss, mid, qs, qe, 2 * idx + 1) + query(mid + 1, se, qs, qe, 2 * idx + 2);
}

int main() {
    fio;
    //ifstream pfin("input1.txt");
    //ofstream pfout("output1.txt");
    int n, i, m;
    lli u, v, val, x, p, sum, q, ans;
    cin >> n >> m;
    lli a[n];

    for (lli i = 0; i < n; i++)
      cin >> a[i];
    vector < lli > vc[n];
    f(i, 0, n - 1) {
      cin >> u >> v;
      u--;
      v--;
      vc[u].pb(v);
      vc[v].pb(u);
    }
    memset(lazy, 0, sizeof(lazy));
    memset(st, 0, sizeof(st));
    memset(ed, 0, sizeof(ed));

    et(vc, 0, -1); // call euler tour on tree

    build(a, 0, n - 1, 0); // build segment tree
    while (m--) {
      cin >> x;
      if (x == 1) {
        cin >> u >> val;
        u--;
        sum = query(0, n - 1, st[u], ed[u], 0);
        if (sum & 1) // if subtree sum odd then update with 1
          update(0, n - 1, st[u], ed[u], 0, 1);
        else // if subtree sum even then update with val
          update(0, n - 1, st[u], ed[u], 0, val);
      } else {
        cin >> u >> v;
        u--;
        v--;
        p = query(0, n - 1, st[u], ed[u], 0); // get subtree sum for node u
        q = query(0, n - 1, st[v], ed[v], 0); // get subtre sum for node v
        ans = p ^ q;
        cout << ans << endl;
      }
    }
3 Likes

I just wanted to type 20 characters :slightly_smiling_face:

Because this is probably most underrated Editorial for some classical problem and its really cool.

2 Likes

Sorry i tried to figure out why the Euler Path is 1 3 2 5 4; And i could not. Can you give explanation for the same.

I tried referring the above blog but i couldn’t make out…

1 Like