How to solve this problem ?!!

Правка en1, от Zahid_Hasan_Sahin, 2021-05-16 09:35:54

I'm trying to solve Farthest Nodes in a Tree (II) Problem in java . it's from lightOj.But I'm getting MLE(it takes 151552 KB memory).How to solve it using java.

my code :


import java.util.ArrayList; import java.util.Scanner; import java.io.IOException; import java.io.PrintWriter; public class FarthestNodesinaTree { public static void main(String args[]) throws IOException { Scanner scan = new Scanner(System.in); int t = scan.nextInt(); int q = 1; PrintWriter out = new PrintWriter(System.out); while (t-- > 0) { mx = 0; short n = (short) scan.nextInt(); ArrayList<Node>[] node = new ArrayList[n]; for (int i = 0; i < n; i++) { node[i] = new ArrayList<Node>(); } for (int i = 0; i < n - 1; i++) { addEdge((short) scan.nextInt(), (short) scan.nextInt(), scan.nextInt(), node); } int[] a = new int[n]; int[] b = new int[n]; findDiameter(a, b, node, n); out.println("Case " + q++ + ":"); for (int i = 0; i < n; i++) { out.println(farNode(i, a, b)); } } out.close(); } static void addEdge(short u, short v, int w, ArrayList<Node>[] node) { { node[u].add(new Node(v, w)); node[v].add(new Node(u, w)); } } static int currNode; static int mx = 0; static void findDiameter(int[] xDis, int[] yDis, ArrayList<Node>[] node, int n) { findDiameterHelper(0, 0, xDis, -1, node); int x = currNode; mx = Integer.MIN_VALUE; findDiameterHelper(x, 0, xDis, -1, node); int y = currNode; mx = Integer.MIN_VALUE; findDiameterHelper(y, 0, yDis, -1, node); } static int farNode(int u, int[] xDis, int[] yDis) { return Math.max(xDis[u], yDis[u]); } static void findDiameterHelper(int u, int w, int[] arr, int par, ArrayList<Node>[] node) { if (w > mx) { mx = w; currNode = u; } arr[u] = w; for (Node child : node[u]) { if (child.v != par) { findDiameterHelper(child.v, child.w + w, arr, u, node); } } } } class Node { short v; int w; Node(short a, int b) { v = a; w = b; } }
Теги lightoj 1257, mle, java, help

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский Zahid_Hasan_Sahin 2021-05-28 06:04:50 62
en4 Английский Zahid_Hasan_Sahin 2021-05-16 18:29:19 4 Tiny change: ' summary="Code">\n\n~~~~' -> ' summary="code:">\n\n~~~~'
en3 Английский Zahid_Hasan_Sahin 2021-05-16 18:27:40 74 Tiny change: 'mar="Code:">\n` impo' -> 'mar="Code: ">\n` impo'
en2 Английский Zahid_Hasan_Sahin 2021-05-16 09:36:45 6
en1 Английский Zahid_Hasan_Sahin 2021-05-16 09:35:54 2631 Initial revision (published)