Min-Max Weighted Edge | Editorial by aksingh007

Following are the main points that we need to consider
1. if you have atleast one edge which is not the part of any possible diameter then you can put S to that edge.
2. Otherwise output is 0. Else you will put S / (n-1) to each edge. Note that, its ceil will be the minimum possible maximum edge weight.
Hence, the task is just to find that one edge ( if exists) which is not the part of any possible diameter.
It can be solved using simple DFS.
Hence, Time Complexity : O(|V| +|E|)
NOTE: Use Fast I/O

```
import java.util.*;
import java.io.*;
import java.util.*;

class Node{
	int next,weight;boolean ispresent;
	Node(int x,int y,boolean p){next=x;weight=y;ispresent=p;}
	Node(int x,int y){next=x;weight=y;ispresent=true;}
}
class Distance implements Comparable<Distance>{
	int vertex,distance;
	Distance(int v,int d){vertex=v;distance=d;}
	public int compareTo(Distance obj){
		return this.distance-obj.distance;
	}
}
@SuppressWarnings("unchecked")
class Graph{
	int N;
	int dia=0;
	ArrayList<Node> adj[];
	int mat[][];
	Graph(int n){
		N=n+1;
		mat=new int[n+1][n+1];
		adj=new ArrayList[n+1];
		for(int i=0;i<=n;adj[i++]=new ArrayList<Node>());
	}
	void push_edge(int x,int y,int w){
		adj[x].add(0,new Node(y,w));
		adj[y].add(0,new Node(x,w));
		mat[x][y]=mat[y][x]=1;
	}
	
	void bfs(int src,int dist){
		HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
		Queue<Integer> queue=new LinkedList<Integer>();
		int level[]=new int[N];int lvl=1;
		boolean visited[]=new boolean[N];
		queue.offer(src);
		level[src]=1;
		visited[src]=true;
		hm.put(src,-1);
		while(!queue.isEmpty()){
			int cur=queue.poll();
			lvl=level[cur]+1;
			visited[cur]=true;
			for(int i=0;i<adj[cur].size();i++){
				int next=adj[cur].get(i).next;
				if(!visited[next]){
					queue.offer(next);
					visited[next]=true;
					level[next]=lvl;
					hm.put(next,cur);
				}
			}
		}
		int dest=0;
		for(int i=1;i<N;i++){
		    if(level[i]==dist)
		        dest=i;
		    else continue;
		ArrayList<Integer> path=new ArrayList<Integer>();
		int key=dest;
		do{
			path.add(key);
			key=hm.get(key);
		}while(key!=src);
		path.add(src);
		for(int ii=1;ii<path.size();ii++){
		    int a=path.get(ii-1);int b=path.get(ii);
		    mat[a][b]=mat[b][a]=2;
		}
	}
	}
	int farthest(int src){
		HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
		Queue<Integer> queue=new LinkedList<Integer>();
		int level[]=new int[N];int lvl=1;
		boolean visited[]=new boolean[N];
		queue.offer(src);
		visited[src]=true;
		level[src]=lvl++;
		hm.put(src,-1);
		while(!queue.isEmpty()){
			int cur=queue.poll();
			visited[cur]=true;
			lvl=level[cur]+1;
			for(int i=0;i<adj[cur].size();i++){
				int next=adj[cur].get(i).next;
				if(!visited[next]){
					queue.offer(next);
					visited[next]=true;
					level[next]=lvl;
					hm.put(next,cur);
				}
			}
		}
		int max=0;int ret=1;
		for(int i=1;i<N;i++)
		    if(max<level[i]){
		        max=level[i];
		        ret=i;
		      }
		    dia=max;
		return ret;
	}
	
	int ans(int n,int sum){
	   n--;
	    for(int i=1;i<N;i++)
	        for(int j=i+1;j<N;j++)
	            if(mat[i][j]==1 || mat[j][i]==1)
	                return 0;
	    return sum/n+(sum%n==0?0:1);
	}
}
	
	
class GraphAlgos{
	public static void main(String args[]) throws Exception{
		//Reader sc=new Reader();
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		Scanner sc=new Scanner(System.in);
		int t=Integer.parseInt(br.readLine());
		while(t-->0){
		    String ns[]=br.readLine().split(" ");
		    //int n=sc.nextInt();
		    //int s=sc.nextInt();
		    int n=Integer.parseInt(ns[0]);
		    int s=Integer.parseInt(ns[1]);
		    Graph graph = new Graph(n+1);
		    for(int i=0;i<n-1;i++){
		        String uv[]=br.readLine().split(" ");
		        graph.push_edge(Integer.parseInt(uv[0]),Integer.parseInt(uv[1]),0);
		    }
		    int f=graph.farthest(1);
		    int far=graph.farthest(f);
		    for(int i=1;i<=n;i++)
		        graph.bfs(i,graph.dia);
		    System.out.println(graph.ans(n,s));
		}
	}
}

```

Min-Max Weighted Edge | Editorial by aksingh007

Download submission

All caught up!

View submission

Is your resume even shortlisted?