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