結果

問題 No.386 貪欲な領主
コンテスト
ユーザー Grenache
提出日時 2016-07-01 23:17:51
言語 Java
(openjdk 23)
結果
AC  
実行時間 543 ms / 2,000 ms
コード長 4,453 bytes
コンパイル時間 3,640 ms
コンパイル使用メモリ 80,116 KB
実行使用メモリ 81,856 KB
最終ジャッジ日時 2024-10-12 19:05:56
合計ジャッジ時間 8,071 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

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();

		@SuppressWarnings("unchecked")
		ArrayList<Integer>[] edges = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			edges[i] = new ArrayList<Integer>();
		}

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

		LCA lca = new LCA(edges, 0);

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

		long[] sum = new long[n];
		sum[0] = u[0];
		boolean[] used = new boolean[n];
		Queue<Integer> q = new ArrayDeque<>();
		q.add(0);
		used[0] = true;
		while (!q.isEmpty()) {
			int e = q.remove();

			for (int next : edges[e]) {
				if (used[next]) {
					continue;
				}
				sum[next] = u[next] + sum[e];
				used[next] = true;
				q.add(next);
			}
		}

		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;
		ArrayList<Integer>[] edges;

		LCA(ArrayList<Integer>[] edges, int root) {
			this.edges = edges;
			n = edges.length;
			logn = (int)(Math.log(n) / Math.log(2));

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

			dfs(root, -1, 0);

			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]];
					}
				}
			}
		}

		private void dfs(int v, int p, int d) {
			parent[0][v] = p;
			depth[v] = d;

			for (int e : edges[v]) {
				if (e != p) {
					dfs(e, v, d + 1);
				}
			}

		}

		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];
		}

		public int getDepth(int a) {
			return depth[a];
		}

		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;
		StreamTokenizer st;

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

		String next() throws RuntimeException  {
			try {
				if (st.nextToken() != StreamTokenizer.TT_WORD) {
					throw new InputMismatchException();
				}

				return st.sval;

			} catch (IOException e) {
				throw new IllegalStateException();
			}
		}

		int nextInt() throws RuntimeException {
			try {
				if (st.nextToken() != StreamTokenizer.TT_NUMBER) {
					throw new InputMismatchException();
				}

				return (int)st.nval;

			} catch (IOException e) {
				throw new IllegalStateException();
			}
		}

		long nextLong() throws RuntimeException {
			try {
				if (st.nextToken() != StreamTokenizer.TT_NUMBER) {
					throw new InputMismatchException();
				}

				return (long)st.nval;

			} catch (IOException e) {
				throw new IllegalStateException();
			}
		}

		float nextFloat() throws RuntimeException {
			try {
				if (st.nextToken() != StreamTokenizer.TT_NUMBER) {
					throw new InputMismatchException();
				}

				return (float)st.nval;

			} catch (IOException e) {
				throw new IllegalStateException();
			}
		}

		double nextDouble() throws RuntimeException {
			try {
				if (st.nextToken() != StreamTokenizer.TT_NUMBER) {
					throw new InputMismatchException();
				}

				return st.nval;

			} catch (IOException e) {
				throw new IllegalStateException();
			}
		}

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

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