Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Edge Strength (Lowe) problem solution

YASH PAL, 31 July 2024
In this HackerEarth Edge Strength (Lowe) problem solution Monk is given a tree rooted at node 1.The tree has N nodes and N – 1 edges. Each edge has some strength associated with it. The strength of an edge is determined by the number of pair of nodes which are connected with the help of that particular edge.
Alternatively consider all the paths between every pair of nodes and the strength of an edge will be equal to the number of paths in which that edge comes.
Monk wants to know the strength of each edge of the tree.
Note: Node pair (i,j) is same as node pair (j,i).
HackerEarth Edge Strength (Lowe) problem solution

HackerEarth Edge Strength (Lowe) problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll n;
vector<ll>v[100005];
ll subtree[100005],par[100005],vis[100005];
vector<pair<ll,ll> >edge;
void dfs(ll node)
{
vis[node]=1;
subtree[node]=1;
ll i,j;
for(i=0;i<v[node].size();i++)
{
j=v[node][i];
if(!vis[j])
{
par[j]=node;
dfs(j);
subtree[node]+=subtree[j];
}
}
}
int main()
{
//freopen("inp16.txt","r",stdin);
//freopen("out16.txt","w",stdout);
ll i,j,k,x,y;
cin>>n;
cin>>x>>y;
for(i=1;i<n;i++)
{
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
edge.push_back({x,y});
}
dfs(1);
for(i=0;i<edge.size();i++)
{
x=edge[i].first;
y=edge[i].second;
if(par[x]!=y)
swap(x,y);
cout<<(n-subtree[x])*subtree[x]<<"n";
}
return 0;
}

Second solution

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<int>v[100005];
int val[100005];
bool vis[100005];
void dfs(int u)
{
vis[u]=1;val[u]=1;
for(int i=0;i<v[u].size();i++)
{
if(!vis[v[u][i]])
{
dfs(v[u][i]);
val[u]+=val[v[u][i]];
}
}
}
int main()
{
int n;
cin>>n;
assert(n>=1 && n<=1e5);
vector<pair<int,int> >edge;
int row,col;cin>>row>>col;
for(int i=1;i<=row;i++)
{
int x,y;
cin>>x>>y;
assert(x>=1 && x<=n);
assert(y>=1 && y<=n);
assert(x!=y);
edge.push_back(make_pair(x,y));
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1);ll ans=0;
for(int i=0;i<edge.size();i++)
{
int a=edge[i].first,b=edge[i].second;
ll x=min(val[a],val[b]);
cout<<x*(n-x)<<"n";
}
return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

Related website

The Computer Science

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes