結果

問題 No.898 tri-βutree
ユーザー htensaihtensai
提出日時 2020-06-10 20:02:27
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,977 ms / 4,000 ms
コード長 2,245 bytes
コンパイル時間 4,285 ms
コンパイル使用メモリ 83,232 KB
実行使用メモリ 138,084 KB
最終ジャッジ日時 2023-08-08 16:50:58
合計ジャッジ時間 37,940 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,558 ms
138,084 KB
testcase_01 AC 123 ms
56,132 KB
testcase_02 AC 176 ms
55,920 KB
testcase_03 AC 178 ms
56,068 KB
testcase_04 AC 169 ms
55,788 KB
testcase_05 AC 167 ms
55,924 KB
testcase_06 AC 169 ms
56,096 KB
testcase_07 AC 1,921 ms
121,160 KB
testcase_08 AC 1,924 ms
121,088 KB
testcase_09 AC 1,878 ms
123,336 KB
testcase_10 AC 1,885 ms
123,160 KB
testcase_11 AC 1,887 ms
121,340 KB
testcase_12 AC 1,894 ms
121,936 KB
testcase_13 AC 1,926 ms
121,648 KB
testcase_14 AC 1,890 ms
121,080 KB
testcase_15 AC 1,880 ms
121,812 KB
testcase_16 AC 1,915 ms
121,804 KB
testcase_17 AC 1,935 ms
122,700 KB
testcase_18 AC 1,903 ms
124,080 KB
testcase_19 AC 1,911 ms
121,096 KB
testcase_20 AC 1,977 ms
121,788 KB
testcase_21 AC 1,957 ms
121,424 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