给定一棵树，为每个边缘分配权重，以最小化树中每个路径（u，v）的权重

给定一棵树，为每个边缘分配权重，以最小化树中每个路径（u，v）的权重。为了澄清，我们正在最小化树中每个路径上的最大权重 这个问题可以用某种数据结构或算法解决吗？您如何确定要放在树的每个边缘上的权重？输入的数字为N，您必须在树的每个边缘上将权重置于[0，N-2]（包括）值之间。

让我澄清这个问题。假设您有一条边（1、2），并且在该边上放置了权重3。问题中“权重”的实际定义是[u，v）路径中不存在的[0，N-2]中的最小值。即使特定边上的权重为三，但在问题中的实际权重为零。另外，此问题中树的根是1。

我针对这个问题的原始方法是将[0，N-2]中的值（我们可以分配给每个边的边值）添加到堆栈中，然后使用DFS遍历树并从堆栈中弹出一个值（最大值-最边缘值）并将其分配给边缘。然而，这并未使所有路径上的成本最小化。请记住，成本是（u，v）路径上不存在的最小值-最大值。我们正在努力降低成本，以使每条可能的路径上的成本降至最低。

我的代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Stack;
import java.util.Iterator;
import java.util.ArrayList;
    public class Mex    {
        public static void main (String [] args) throws IOException {
            BufferedReader b1 = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(b1.readLine());
            LinkedList<Integer>[] adj = new LinkedList[n+1];
            ArrayList<Integer> v = new ArrayList<Integer>(n+1);
            for(int i = 1; i<=n; i++) {
                adj[i] = new LinkedList<Integer>();
            }
            for(int i = 0; i<n-1; i++) {
                String [] edge = (b1.readLine()).split(" ");
                adj[Integer.parseInt(edge[0])].add(Integer.parseInt(edge[1]));
                adj[Integer.parseInt(edge[1])].add(Integer.parseInt(edge[0]));
                v.add(Integer.parseInt(edge[0]));
                v.add(Integer.parseInt(edge[1]));
            }
            dfs(adj, 1, n, v);


        }
        static void dfs(LinkedList<Integer> adj[], int u, int n, ArrayList<Integer> order)   { 
            Stack<Integer> values = new Stack<>();
            int [][] weight = new int[n+1][n+1];
            for(int i = 0; i<n-1; i++) {
                values.push(i);
            }
            boolean [] visited = new boolean[n+1];
            int [] parent = new int[n+1];
            for (int i = 1; i < n+1; i++) 
                visited[i] = false; 

            Stack<Integer> stack = new Stack<>(); 

            stack.push(u); 

            while(stack.empty() == false) { 
                u = stack.peek(); 
                stack.pop(); 

                if(visited[u] == false)  { 
                  visited[u]  = true; 
                  if(u!= 1) {
                    if(adj[u].size()==1) {
                        if(values.contains(0)) {
                            weight[parent[u]][u] = 0;
                            values.remove(0);
                        }
                        else {
                            int w = values.pop();
                            weight[parent[u]][u] = w;
                        }
                    }
                    else {
                        int w = values.pop();
                        weight[parent[u]][u] = w;   
                    }
                  }
                } 

                Iterator<Integer> itr = adj[u].iterator(); 

                while (itr.hasNext())  {                    
                    int v = itr.next(); 
                    if(parent[v]==0 && v!=1) {
                        parent[v] = u;
                    }
                    if(!visited[v]) 
                        stack.push(v); 
                } 

            } 
            for(int i = 0; i<order.size()-1; i+=2) {
                if(parent[order.get(i)]==order.get(i+1)) {
                    System.out.println(weight[order.get(i+1)][order.get(i)]);               
                }
                else {
                    System.out.println(weight[order.get(i)][order.get(i+1)]);               
                }
            }
        } 
    }

问题来源：Stack Overflow