In this

**HackerEarth Path queries problem solution**, You are given an undirected tree G with N nodes. Every node is assigned a value denoted by .A simple path u1 - u2 - u3 - u4,..., -uk is said to be beautiful if the number of pairs of nodes (ui, ui+1) where A[ui] is odd and A[ui + 1] is even and number of pairs of nodes (ui, ui+1) where A[ui] is even and A[ui + 1] is odd are equal.

Given Q queries of the form:

u val: Set the value of node n equal to val, i.e. set A[u] = val and find the number of ordered pairs (u,v) such that the simple path between node u and node v is beautiful.

## hackerEarth Path queries problem solution.

`#include<bits/stdc++.h>`

#define int long long int

using namespace std;

void solve(){

int n, q;

cin >> n >> q;

assert(1 <= n and n <= 200000);

assert(1 <= q and q <= 200000);

int a[n + 1];

int c_e = 0;

int c_o = 0;

for(int i = 1 ; i <= n ; i++)

{

cin >> a[i];

assert(1 <= a[i] and a[i] <= 1000000000);

if(a[i]%2) c_o++;

else c_e++;

}

for(int i = 1 ; i <= n - 1 ; i++){

int u, v;

cin >> u >> v;

assert(1 <= u and u <= n);

assert(1 <= v and v <= n);

assert(u != v);

}

while(q--)

{

int u, val;

cin >> u >> val;

assert(1 <= u and u <= n);

assert(1 <= val and val <= 1000000000);

if(a[u]%2) c_o--;

else c_e--;

a[u] = val;

if(a[u]%2) c_o++;

else c_e++;

int answer = (c_e*(c_e - 1))/2;

answer += (c_o*(c_o - 1))/2;

answer += (c_o + c_e);

cout << answer << " ";

}

cout << endl;

}

signed main(){

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int t;

cin >> t;

assert(1 <= t and t <= 10);

while(t--){

solve();

}

}

## 0 Comments