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
Programmingoneonone

HackerEarth Min-Max Weighted Edge problem solution

YASH PAL, 31 July 2024
In this HackerEarth Min-Max Weighted Edge problem solution Given a tree with N nodes and N – 1 bidirectional edge and given an integer S. Now, you have to assign the weights to the edges of this tree such that:
  1. the sum of the weights of all the edges is equal to S.
  2. for every possible diameter of the tree, the maximum weight over all the edges covered by its path is the minimum possible.
You have to output this minimum possible edge weight.
HackerEarth Min-Max Weighted Edge problem solution

HackerEarth Min-Max Weighted Edge problem solution.

#include <bits/stdc++.h>

using namespace std;

const int N = 2E3 + 5;
int len;
int d_len;
int start;
int vis[N];
int path[N];
set<int> nodes;
vector<int> v[N];

void dfs(int src) {
len ++;
if(len > d_len) {
d_len = len;
start = src;
}
vis[src] = 1;
for(auto i : v[src]) {
if(!vis[i])
dfs(i);
}
len --;
return;
}

void dfs_again(int src) {
len ++;
vis[src] = 1;
path[len] = src;
if(len == d_len) {
for(int i = 1; i <= len; i ++)
nodes.insert(path[i]);
}
for(auto i : v[src]) {
if(!vis[i])
dfs_again(i);
}
len --;
return;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t --) {
int n, s;
cin >> n >> s;
int x, y;
for(int i = 1; i < n; i ++) {
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}

len = d_len = 0;
memset(vis, 0, sizeof vis);
dfs(1);
len = d_len = 0;
memset(vis, 0, sizeof vis);
dfs(start);
for(int i = 1; i <= n; i ++) {
len = 0;
memset(vis, 0, sizeof vis);
dfs_again(i);
}
bool not_fnd = 0;
for(int i = 1; i <= n; i ++) {
if(nodes.find(i) == nodes.end()) {
not_fnd = 1;
break;
}
}
int ans = 0;
if(!not_fnd) {
ans = s / (n - 1);
if(s % (n - 1) != 0)
ans ++;
}
cout << ans << 'n';
nodes.clear();
for(int i = 1; i <= n; i ++)
v[i].clear();
}
return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

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