結果

問題 No.898 tri-βutree
ユーザー htensaihtensai
提出日時 2020-06-10 20:02:27
言語 Java21
(openjdk 21)
結果
AC  
実行時間 2,359 ms / 4,000 ms
コード長 2,245 bytes
コンパイル時間 3,298 ms
コンパイル使用メモリ 85,640 KB
実行使用メモリ 126,968 KB
最終ジャッジ日時 2024-11-08 23:45:50
合計ジャッジ時間 45,144 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,596 ms
126,968 KB
testcase_01 AC 136 ms
41,316 KB
testcase_02 AC 196 ms
41,764 KB
testcase_03 AC 191 ms
42,048 KB
testcase_04 AC 192 ms
42,032 KB
testcase_05 AC 182 ms
41,984 KB
testcase_06 AC 183 ms
41,856 KB
testcase_07 AC 2,285 ms
115,808 KB
testcase_08 AC 2,359 ms
118,032 KB
testcase_09 AC 2,310 ms
118,796 KB
testcase_10 AC 2,249 ms
118,540 KB
testcase_11 AC 2,321 ms
117,996 KB
testcase_12 AC 2,304 ms
115,536 KB
testcase_13 AC 2,250 ms
118,048 KB
testcase_14 AC 2,347 ms
115,564 KB
testcase_15 AC 2,277 ms
118,292 KB
testcase_16 AC 2,312 ms
118,056 KB
testcase_17 AC 2,355 ms
115,668 KB
testcase_18 AC 2,339 ms
118,284 KB
testcase_19 AC 2,329 ms
115,544 KB
testcase_20 AC 2,345 ms
118,328 KB
testcase_21 AC 2,309 ms
117,484 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

public class Main {
    static int[][] parents;
    static long[] dists;
    static int[] depth;
    static ArrayList<HashMap<Integer, Integer>> graph = new ArrayList<>();
 	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
	    int n = sc.nextInt();
	    for (int i = 0; i < n; i++) {
	        graph.add(new HashMap<>());
	    }
	    for (int i = 0; i < n - 1; i++) {
	        int a = sc.nextInt();
	        int b = sc.nextInt();
	        int c = sc.nextInt();
	        graph.get(a).put(b, c);
	        graph.get(b).put(a, c);
	    }
	    parents = new int[n][18];
	    dists = new long[n];
	    depth = new int[n];
	    setParent(0, 0, 0, 0);
	    for (int i = 1; i < 18; i++) {
	        for (int j = 0; j < n; j++) {
	            parents[j][i] = parents[parents[j][i - 1]][i - 1];
	        }
	    }
	    int q = sc.nextInt();
	    StringBuilder sb = new StringBuilder();
	    for (int i = 0; i < q; i++) {
	        sb.append(getValue(sc.nextInt(), sc.nextInt(), sc.nextInt())).append("\n");
	    }
	    System.out.print(sb);
	}
	
	static void setParent(int idx, int parent, long value, int dep) {
	    parents[idx][0] = parent;
	    dists[idx] = value;
	    depth[idx] = dep;
	    for (Map.Entry<Integer, Integer> entry : graph.get(idx).entrySet()) {
	        if (entry.getKey() == parent) {
	            continue;
	        }
	        setParent(entry.getKey(), idx, value + entry.getValue(), dep + 1);
	    }
	}
	
	static long getValue(int a, int b, int c) {
	    return (getValue(a, b) + getValue(b, c) + getValue(c, a)) / 2;
	}
	
	static long getValue(int a, int b) {
	    int c = getLCA(a, b);
	    return dists[a] + dists[b] - dists[c] * 2;
	}
	
	static int getLCA(int a, int b) {
	    if (depth[a] > depth[b]) {
	        return getLCA(b, a);
	    }
	    for (int i = 17; i >= 0 && depth[a] < depth[b]; i--) {
	        if (depth[b] - depth[a] >= (1 << i)) {
	            b = parents[b][i];
	        }
	    }
	    for (int i = 17; i >= 0 && a != b; i--) {
	        if (parents[a][i] != parents[b][i]) {
	            a = parents[a][i];
	            b = parents[b][i];
	        }
	    }
	    if (a != b) {
	        a = parents[a][0];
	        b = parents[b][0];
	    }
	    return a;
	}
}
0