### Zahid_Hasan_Sahin's blog

By Zahid_Hasan_Sahin, history, 4 weeks ago,

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.??

code:

UPD:Using System.gc() after each testCase I have got AC.

• 0

 » 4 weeks ago, # |   0 Try writing iterative dfs, or maybe just write a bfs instead.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Again MLE.memory used 151552 KB. code:import java.util.ArrayList; import java.util.Scanner; import java.io.IOException; import java.io.PrintWriter; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; 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; int n = scan.nextInt(); ArrayList[] node = new ArrayList[n]; for (int i = 0; i < n; i++) { node[i] = new ArrayList(); } for (int i = 0; i < n - 1; i++) { addEdge(scan.nextInt(), 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(int u, int v, int w, ArrayList[] 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, int n) { findDiameterHelper(0, 0, xDis, node, n); int x = currNode; for (int i = 0; i < n; i++) { xDis[i] = 0; } mx = Integer.MIN_VALUE; findDiameterHelper(x, 0, xDis, node, n); int y = currNode; mx = Integer.MIN_VALUE; findDiameterHelper(y, 0, yDis, node, n); } 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, ArrayList[] node, int n) { Queue q = new LinkedList(); q.add(u); boolean[] vis = new boolean[n]; vis[u] = true; while (!q.isEmpty()) { int curr = q.poll(); if (arr[curr] > mx) { mx = arr[curr]; currNode = curr; } vis[curr] = true; for (Node child : node[curr]) { if (!vis[child.v]) { arr[child.v] = child.w + arr[curr]; q.add(child.v); } } } } } class Node { int v; int w; Node(int a, int b) { v = a; w = b; } } 
•  » » » 4 weeks ago, # ^ |   0 In the future, I would suggest you use Java's StringTokenizer and BufferedReader. Java's Scanner class is notoriously known for getting TLE or faster runtimes.
•  » » » » 4 weeks ago, # ^ |   0 I use fast i/o.but for Simplicity i have share this code without any extra code.Btw my problem isn't TLE, problem is MLE. :(