➤ Problem Link : 1325C. Ehab and Path
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int n;
vector<int> adj[100001];
vector<pair<int,int> > edges;
vector<pair<int,int> > srt;
map<pair<int,int>,ll > mp;
ll sz[100001];
bool comp(pair<int,int> x, pair<int,int> y)
{
return mp[x]<mp[y];
}
ll dfs1(int v,int p)
{
sz[v]=1;
for(int i=0;i<adj[v].size();i++)
{
if(adj[v][i]==p)
continue;
sz[v]+=dfs1(adj[v][i],v);
// cout<<v<<" "<<sz[v]<<endl;
}
return sz[v];
}
void dfs2(int v,int p)
{
pair<int,int> pr=make_pair(min(v,p),max(p,v));
mp[pr]=sz[v]*(sz[1]-sz[v]);
// cout<<p<<" "<<v<<" "<<mp[pr]<<endl;
for(int i=0;i<adj[v].size();i++)
{
if(adj[v][i]==p)
continue;
dfs2(adj[v][i],v);
}
}
int main()
{
cin>>n;
int u,v;
for(int i=1;i<n;i++)
{
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
edges.push_back(make_pair(min(u,v),max(u,v)));
srt.push_back(make_pair(min(u,v),max(u,v)));
}
dfs1(1,-1);
for(int i=0;i<adj[1].size();i++)
{
dfs2(adj[1][i],1);
}
sort(srt.begin(),srt.end(),comp);
// cout<<srt[0].first<<srt[0].second<<endl;
int q=0;
for(int i=0;i<srt.size();i++)
mp[srt[i]]=q++;
for(int i=0;i<edges.size();i++)
cout<<mp[edges[i]]<<"\n";
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.