結果

問題 No.386 貪欲な領主
ユーザー Grenache
提出日時 2016-07-01 23:17:51
言語 Java8
(openjdk 1.8.0.222)
結果
AC  
実行時間 510 ms
コード長 4,453 Byte
コンパイル時間 2,550 ms
使用メモリ 65,328 KB
最終ジャッジ日時 2019-08-22 19:08:47

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
test1.txt AC 75 ms
19,284 KB
test2.txt AC 75 ms
19,276 KB
test3.txt AC 74 ms
19,288 KB
test4.txt AC 74 ms
19,288 KB
test5.txt AC 510 ms
65,324 KB
test6.txt AC 501 ms
49,016 KB
test7.txt AC 505 ms
48,956 KB
test8.txt AC 95 ms
20,412 KB
test9.txt AC 161 ms
23,404 KB
test10.txt AC 104 ms
20,500 KB
test11.txt AC 73 ms
19,280 KB
test12.txt AC 73 ms
19,276 KB
test13.txt AC 88 ms
20,372 KB
test14.txt AC 119 ms
21,416 KB
test15.txt AC 510 ms
49,012 KB
test16.txt AC 479 ms
65,328 KB
テストケース一括ダウンロード

ソースコード

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