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