結果

問題 No.898 tri-βutree
ユーザー htensaihtensai
提出日時 2020-06-10 20:02:27
言語 Java21
(openjdk 21)
結果
AC  
実行時間 2,539 ms / 4,000 ms
コード長 2,245 bytes
コンパイル時間 3,669 ms
コンパイル使用メモリ 79,676 KB
実行使用メモリ 127,144 KB
最終ジャッジ日時 2024-04-26 09:28:23
合計ジャッジ時間 43,866 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,570 ms
127,144 KB
testcase_01 AC 116 ms
40,036 KB
testcase_02 AC 178 ms
42,496 KB
testcase_03 AC 179 ms
41,964 KB
testcase_04 AC 206 ms
42,200 KB
testcase_05 AC 191 ms
42,076 KB
testcase_06 AC 179 ms
42,160 KB
testcase_07 AC 2,539 ms
115,544 KB
testcase_08 AC 2,312 ms
115,344 KB
testcase_09 AC 2,297 ms
118,564 KB
testcase_10 AC 2,243 ms
118,612 KB
testcase_11 AC 2,290 ms
115,840 KB
testcase_12 AC 2,275 ms
118,500 KB
testcase_13 AC 2,270 ms
115,660 KB
testcase_14 AC 2,300 ms
118,020 KB
testcase_15 AC 2,301 ms
117,992 KB
testcase_16 AC 2,337 ms
118,128 KB
testcase_17 AC 2,297 ms
116,512 KB
testcase_18 AC 2,290 ms
117,860 KB
testcase_19 AC 2,303 ms
118,028 KB
testcase_20 AC 2,323 ms
118,412 KB
testcase_21 AC 2,280 ms
116,220 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