In this HackerEarth Separating Numbers problem solution We are given a tree with N nodes. Each node has a color Ci. We are also given N-1 queries and in each query we are told to destroy a previously undestroyed edge. Every time we destroy an edge, we have to report the number of pairs of nodes that get disconnected. Here, two nodes i and j are said to be disconnected  if before the destruction you could reach from i to j using edges not yet destroyed , and if Ci = Cj.

HackerEarth Separating Numbers problem solution

HackerEarth Separating Numbers problem solution.

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
//#define int long long
#define ld long double
#define vi deque<int>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define il pair<int,ll>
#define pll pair<ll,ll>
#define _path pair<ll,pair<ll,int> >
#define vv deque
//#define endl '\n'
//#define mp make_pair

using namespace std;

const int MAXN = 3e5+5;
const ll INF = 1e18;

vi g[MAXN];

struct DSU{
int parent[MAXN];
int sz[MAXN];
map<int,ll> mp[MAXN];
DSU(int* arr,int n){
FOR(i,n)parent[i] = i;
FOR(i,n)sz[i] = 1;
FOR(i,n)mp[i][arr[i]] = 1;

int find(int a){
if(parent[a] != a)parent[a] = find(parent[a]);
return parent[a];

ll merge(int a,int b){
int pa = find(a);
int pb = find(b);
ll sum = 0;
if(sz[pa] < sz[pb])swap(pa,pb);
for(auto e: mp[pb]){
sum +=*mp[pa][e.ff];
mp[pa][e.ff] +=;
sz[pa] += sz[pb];
parent[pb] = pa;
return sum;

void solve(){
int n,q;
cin >> n;
q = n-1;
ii edge[n];
int a,b;
cin >> a >> b;
edge[i] = {a,b};
int colors[n];
FOR(i,n)cin >> colors[i];
DSU dsu(colors,n);
int queries[q];
int x;
cin >> x;
queries[i] = x;
ll ans[q];
for(int i = q-1;i >= 0;i--){
ans[i] = dsu.merge(edge[queries[i]].ff,edge[queries[i]].ss);
cout << ans[i] << endl;

int main(){

int t = 1;
return 0;