I was trying to solve SPOJ EAGLE1 and used the in-out DP method to solve it. Even though I feel like i have a really fast solution in my code, yet i am getting TLE. Any help will be appreciated.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String args[]) throws IOException {
Scan sc = new Scan();
Print pt = new Print();
int t = sc.scanInt();
Solution sol = new Solution();
while(t-- > 0){
int N = sc.scanInt();
sol.reset(N);
for(int i = 1; i < N; ++i)
sol.addEdge(sc.scanInt(), sc.scanInt(), sc.scanInt());
sol.solve();
for(int i = 1; i <= N; ++i)
pt.print((sol.in[i] > sol.out[i] ? sol.in[i] : sol.out[i]) + " ");
pt.println();
}
pt.close();
}
}
class Solution {
// ArrayList<Node>[] adjList = new ArrayList[100001];
// long[] in = new long[100001];
// long[] out = new long[100001];
// long[] max_1 = new long[100001];
// long[] max_2 = new long[100001];
// int[] maxChild_1 = new int[100001];
// int N;
ArrayList<Node>[] adjList;
long[] in,out,max_1,max_2;
int[] maxChild_1;
int N;
void reset(int N){
this.N = N;
// for(int i = 1; i <= N; ++i){
// in[i] = 0;
// out[i] = 0;
// max_1[i] = 0;
// max_2[i] = 0;
// maxChild_1[i] = 0;
// if(adjList[i] == null)
// adjList[i] = new ArrayList<Node>(N>>1);
// else
// adjList[i].clear();
// }
in = new long[N+1];
out = new long[N+1];
max_1 = new long[N+1];
max_2 = new long[N+1];
maxChild_1 = new int[N+1];
adjList = new ArrayList[N+1];
for(int i = 1; i <= N; ++i)
adjList[i] = new ArrayList<Node>();
}
void addEdge(int a, int b, long wt){
adjList[a].add(new Node(b, wt));
adjList[b].add(new Node(a, wt));
}
long dfs(int parent, int start){
long max1 = 0;
long max2 = 0;
int maxChild1 = 0;
int maxChild2 = 0;
for(Node nbr : adjList[start]){
if(nbr.id == parent)
continue;
long tempMax = nbr.wt + dfs(start, nbr.id);
if(tempMax > max1){
max2 = max1;
max1 = tempMax;
maxChild2 = maxChild1;
maxChild1 = nbr.id;
}
else if(tempMax > max2){
max2 = tempMax;
maxChild2 = nbr.id;
}
}
max_1[start] = max1;
max_2[start] = max2;
maxChild_1[start] = maxChild1;
in[start] = max1;
return max1;
}
void dfs2(int parent, int start){
for(Node nbr : adjList[start]){
if(nbr.id == parent)
continue;
long tmp = out[start];
if(nbr.id == maxChild_1[start]){
out[nbr.id] = nbr.wt + (tmp > max_2[start] ? tmp : max_2[start]);
}
else {
out[nbr.id] = nbr.wt + (tmp > max_1[start] ? tmp : max_1[start]);
}
dfs2(start, nbr.id);
}
}
void solve(){
dfs(0, 1);
dfs2(0, 1);
}
}
class Node {
int id;
long wt;
Node(int id, long wt){
this.id = id;
this.wt = wt;
}
}
// fast I/O
class Scan
{
private byte[] buf=new byte[1024]; //Buffer of Bytes
private int index;
private InputStream in;
private int total;
public Scan()
{
in=System.in;
}
public int scan()throws IOException //Scan method used to scan buf
{
if(index>=total)
{
index=0;
total=in.read(buf);
if(total<=0)
return -1;
}
return buf[index++];
}
public int scanInt()throws IOException
{
int big=0;
int n=scan();
while(isWhiteSpace(n)) //Removing starting whitespaces
n=scan();
int neg=1;
if(n=='-') //If Negative Sign encounters
{
neg=-1;
n=scan();
}
while(!isWhiteSpace(n))
{
if(n>='0'&&n<='9')
{
big*=10;
big+=n-'0';
n=scan();
}
else throw new InputMismatchException();
}
return neg*big;
}
private boolean isWhiteSpace(int n)
{
if(n==' '||n=='\n'||n=='\r'||n=='\t'||n==-1)
return true;
return false;
}
}
class Print
{
private final BufferedWriter bw;
public Print()
{
this.bw=new BufferedWriter(new OutputStreamWriter(System.out));
}
public void print(Object object)throws IOException
{
bw.append(""+object);
}
public void println()throws IOException
{
bw.append("\n");
}
public void close()throws IOException
{
bw.close();
}
}
