結果

問題 No.386 貪欲な領主
ユーザー Grenache
提出日時 2016-07-01 23:17:51
言語 Java8
(openjdk 1.8.0.191)
結果
AC  
実行時間 717 ms
コード長 4,453 Byte
コンパイル時間 2,880 ms
使用メモリ 76,664 KB
最終ジャッジ日時 2019-06-13 07:37:03

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
test1.txt AC 83 ms
31,348 KB
test2.txt AC 85 ms
30,324 KB
test3.txt AC 86 ms
30,608 KB
test4.txt AC 86 ms
31,448 KB
test5.txt AC 630 ms
76,660 KB
test6.txt AC 661 ms
60,604 KB
test7.txt AC 684 ms
59,676 KB
test8.txt AC 108 ms
31,356 KB
test9.txt AC 176 ms
32,120 KB
test10.txt AC 114 ms
30,324 KB
test11.txt AC 86 ms
28,884 KB
test12.txt AC 84 ms
29,964 KB
test13.txt AC 101 ms
30,976 KB
test14.txt AC 137 ms
32,500 KB
test15.txt AC 717 ms
59,128 KB
test16.txt AC 600 ms
76,664 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