結果

問題 No.898 tri-βutree
ユーザー htensai
提出日時 2020-06-10 20:02:27
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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