HackerEarth Path queries problem solution

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();
    }
}

hackerEarth Path queries problem solution.

Leave a Reply