#101191 (Java) No.386 貪欲な領主

• 問題: No.386 貪欲な領主
• ユーザー: Grenache
• 提出日時: 2016-07-02 12:56:46
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 1,035 ms / 2,000 ms
• コード長: 4,333 bytes
• コンパイル時間: 3,617 ms
• コンパイル使用メモリ: 80,380 KB
• 実行使用メモリ: 83,468 KB
• 最終ジャッジ日時: 2024-10-12 19:43:43
• 合計ジャッジ時間: 10,682 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
other	AC * 16

ソースコード

import java.io.*;
import java.util.*;


public class Main_yukicoder386 {

    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	Printer pr = new Printer(System.out);

		int n = sc.nextInt();

		List<List<Integer>> edges = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			edges.add(new ArrayList<>());
		}

		for (int i = 0; i < n - 1; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			edges.get(x).add(y);
			edges.get(y).add(x);
		}

		int root = 0;
		LCA lca = new LCA(edges, root);

		int[] u = new int[n];
		for (int i = 0; i < n; i++) {
			u[i] = sc.nextInt();
		}

		long[] sum = new long[n];
		sum[root] = u[root];
		Queue<Integer> q = new ArrayDeque<>();
		q.add(root);
		while (!q.isEmpty()) {
			int e = q.remove();
			int pe = lca.parent[0][e];

			for (int ne : edges.get(e)) {
				if (ne == pe) {
					continue;
				}
				sum[ne] = u[ne] + sum[e];
				q.add(ne);
			}
		}

		int m = sc.nextInt();
		long ret = 0;
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();

			int lcav = lca.getLCA(a, b);
			ret += c * (sum[a] + sum[b] - 2 * sum[lcav] + u[lcav]);
		}

		pr.println(ret);

        pr.close();
        sc.close();
    }

	@SuppressWarnings("unused")
	private static class LCA {
		int n;
		int logn;
		int[][] parent;
		int[] depth;
		List<List<Integer>> edges;

		// root を根とする edges で表される根付き木からLCAを求める。
		// edges 内のノードは 0-indexed
		LCA(List<List<Integer>> edges, int root) {
			this.edges = edges;
			n = edges.size();
			logn = (int)(Math.log(n) / Math.log(2));

			parent = new int[logn + 1][n];
			depth = new int[n];

			bfs(root, -1, 0);

			// parent[i][j]はノードjの2^i上の親ノード
			for (int i = 1; i <= logn; i++) {
				for (int j = 0; j < n; j++) {
					if (parent[i - 1][j] == -1) {
						parent[i][j] = -1;
					} else {
						parent[i][j] = parent[i - 1][parent[i - 1][j]];
					}
				}
			}
		}

		// v を根として、各ノードの高さ(depth)と親ノード(parent[0])を設定する
		// 根vの高さは0、親は-1
		private void bfs(int v, int p, int d) {
			parent[0][v] = p;
			depth[v] = d;

			Queue<Integer> q = new ArrayDeque<>();
			q.add(v);
			while (!q.isEmpty()) {
				int e = q.remove();
				int pe = parent[0][e];
				int de = depth[e];

				for (int ne : edges.get(e)) {
					if (ne != pe) {
						parent[0][ne] = e;
						depth[ne] = de + 1;
						q.add(ne);
					}
				}
			}
		}

		// ノードaとノードbのLCAを取得する
		public int getLCA(int a, int b) {
			if (depth[a] < depth[b]) {
				int tmp = a;
				a = b;
				b = tmp;
			}

			int diff = depth[a] - depth[b];
			int i = 0;
			while (diff != 0) {
				if ((diff & 0x1) != 0) {
					a = parent[i][a];
				}
				i++;
				diff /= 2;
			}

			if (a == b) {
				return a;
			}

			for ( int k = logn; k >= 0; k--) {
				if (parent[k][a] == parent[k][b]) {
					continue;
				}
				a = parent[k][a];
				b = parent[k][b];
			}

			return parent[0][a];
		}

		// ノードaの高さを取得する
		public int getDepth(int a) {
			return depth[a];
		}

		// ノードa,b間の距離を取得する
		public int getDistance(int a, int b) {
			return depth[a] + depth[b] - 2 * depth[getLCA(a, b)];
		}
	}

	@SuppressWarnings("unused")
	private static class Scanner {
		BufferedReader br;
		Iterator<String> it;

		Scanner (InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}

		String next() throws RuntimeException  {
			try {
				if (it == null || !it.hasNext()) {
					it = Arrays.asList(br.readLine().split(" ")).iterator();
				}
				return it.next();
			} catch (IOException e) {
				throw new IllegalStateException();
			}
		}

		int nextInt() throws RuntimeException {
			return Integer.parseInt(next());
		}

		long nextLong() throws RuntimeException {
			return Long.parseLong(next());
		}

		float nextFloat() throws RuntimeException {
			return Float.parseFloat(next());
		}

		double nextDouble() throws RuntimeException {
			return Double.parseDouble(next());
		}

		void close() {
			try {
				br.close();
			} catch (IOException e) {
//				throw new IllegalStateException();
			}
		}
	}

	private static class Printer extends PrintWriter {
		Printer(PrintStream out) {
			super(out);
		}
	}
}