原本看到相同的題目，想說直接從f163貼程式碼過來就好了

結果在f163可以AC的程式碼，到這裡變成TLE..

不確定是甚麼原因導致TLE 想請大家幫忙確定一下

code:

import java.io.*;

import java.util.*;

public class Main{

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

public static void main(String[] args)throws IOException{

        final int n = readInt(), m = readInt(), n2 = n << 1;

int[] parent = new int[n2], left = new int[n], right = new int[n], weight = new int[n2], w = new int[m];

for(int i = n; i < n2; i++)

weight[i] = readInt(); //the original weight of each container (leaf node)

for(int i = 0; i < m; i++)

w[i] = readInt(); //the wieght of merchandises

        for(int i = 1; i < n; i++){

            int p = readInt(), s = readInt(), t = readInt();

left[p] = s; // s is the left node of p

right[p] = t; // t is the right node of p

parent[t] = parent[s] = p; // p is the parent of s and t;

}

for(int i = n; i < n2; i++){

int j = parent[i]; // j = the parent of i;

//this loop results in TLE

while(j != 1){ // j != root

weight[j] += weight[i]; 

j = parent[j];

}

}

for(int i = 0; i < m; i++){

int j = 1;

while(j < n && left[j] != 0) // ensure j is a leaf node

j = weight[left[j]] <= weight[right[j]] ? left[j] : right[j];

//output

bw.write(Integer.toString(j));

bw.write(" ");

// update the weight of nodes affected

while(j != 1){ 

weight[j] += w[i];

j = parent[j];

}

}

bw.flush();

}

public static int readInt()throws IOException{

int n = 0, c;

        while((c = br.read()) > 47 && c < 58){

n *= 10;

n += c & 15;

        }

        return n;

    }

}

縮排跑掉了

code: https://replit.com/@jam930725/JAVA#Main.java

縮排跑掉了

code: https://replit.com/@jam930725/JAVA#Main.java

我猜只是因為時限縮短而已 最近ZJ一題最多只能10秒

我猜只是因為時限縮短而已 最近ZJ一題最多只能10秒

如果是這樣 那可能就沒辦法了

不過我這題測資#0~#9 都在0.2S內跑完，還沒有到10秒的限制，是在#10TLE之後就結束了

同樣的程式碼 我有在f163再丟了幾次，在測資更大且筆數更多的情況下，還是可以順利AC，所以我才在想會不會是我程式哪裡有問題

我猜只是因為時限縮短而已 最近ZJ一題最多只能10秒

如果是這樣 那可能就沒辦法了

不過我這題測資#0~#9 都在0.2S內跑完，還沒有到10秒的限制，是在#10TLE之後就結束了

同樣的程式碼 我有在f163再丟了幾次，在測資更大且筆數更多的情況下，還是可以順利AC，所以我才在想會不會是我程式哪裡有問題

如果這棵樹非常斜(一直向右偏，然後左邊的數字都比較大的話)，複雜度似乎對JAVA 1.5s不太行(O(NM))，我覺得他是極端測資

我猜只是因為時限縮短而已 最近ZJ一題最多只能10秒

如果是這樣 那可能就沒辦法了

不過我這題測資#0~#9 都在0.2S內跑完，還沒有到10秒的限制，是在#10TLE之後就結束了

同樣的程式碼 我有在f163再丟了幾次，在測資更大且筆數更多的情況下，還是可以順利AC，所以我才在想會不會是我程式哪裡有問題

如果這棵樹非常斜(一直向右偏，然後左邊的數字都比較大的話)，複雜度似乎對JAVA 1.5s不太行(O(NM))，我覺得他是極端測資

我也TLE了...

我猜只是因為時限縮短而已 最近ZJ一題最多只能10秒

如果是這樣 那可能就沒辦法了

不過我這題測資#0~#9 都在0.2S內跑完，還沒有到10秒的限制，是在#10TLE之後就結束了

同樣的程式碼 我有在f163再丟了幾次，在測資更大且筆數更多的情況下，還是可以順利AC，所以我才在想會不會是我程式哪裡有問題

如果這棵樹非常斜(一直向右偏，然後左邊的數字都比較大的話)，複雜度似乎對JAVA 1.5s不太行(O(NM))，我覺得他是極端測資

我也TLE了...

了解

我也TLE了...

我改成用dfs初始化節點重量就AC了

另外...Java還會有StackOverflowError的問題

印象中有人貼過類似的解決方法

不過還是再貼一次

http://codeforces.com/blog/entry/166

我也TLE了...

 

我改成用dfs初始化節點重量就AC了

 

另外...Java還會有StackOverflowError的問題

印象中有人貼過類似的解決方法

不過還是再貼一次

http://codeforces.com/blog/entry/166

分享一下我java的扣（0.3s）:

因為要搞定stackoverflow，變好亂……

import java.io.*;

public class Main implements Runnable{
	public static int ret,r,n,m,w;
	public static int[] ow,nw;
	public static int[][] node,cw;
	public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args) throws IOException {
		new Thread(null,new d105(),"",1<<26).start();
	}
	
	public void run() {
		n=readnum();
		m=readnum();
		ow=new int[n];
		nw=new int[m];
		node=new int[n][2];
		cw=new int[n][2];
		for(int i=0;i<n;i++)ow[i]=readnum();
		for(int i=0;i<m;i++)nw[i]=readnum();
		int f;
		for(int i=0;i<n-1;i++) {
			f=readnum();
			node[f][0]=readnum();
			node[f][1]=readnum();
		}
		setup(1);
		for(int i=0;i<m;i++) {
			w=nw[i];
			put(1);
		}
		try {
			bw.flush();
		} catch (IOException e) {
		}
		System.exit(0);
	}
	
	static int readnum() {
		ret=0;
		try {
			r=br.read();
		} catch (IOException e) {
		}
		while(r>47&&r<58) {
			ret*=10;
			r-=48;
			ret+=r;
			try {r=br.read();} catch (IOException e) {}
		}
		return ret;
	}
	
	static int setup(int x) {
		if(x>=n) {
			return ow[x-n];
		}
		cw[x][0]=setup(node[x][0]);
		cw[x][1]=setup(node[x][1]);
		return cw[x][0]+cw[x][1];
	}
	
	static void put(int x) {
		if(x>=n) {
			try {bw.write(x+" ");} catch (IOException e) {}
			return;
		}
		if(cw[x][0]<=cw[x][1]) {
			cw[x][0]+=w;
			put(node[x][0]);
		}
		else {
			cw[x][1]+=w;
			put(node[x][1]);
		}
	}
}

這題我是用Python測試過，也能AC才上傳的(大概0.7s)

如果不用遞迴的話 要用類似Bfs的方式，透過 queue 來 bottom up 處理，不然可能在worst case可能會變成O(n^2)