Header Ad

HackerEarth Min-Max Weighted Edge problem solution

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

Post a Comment

0 Comments