結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2016-07-02 01:12:30 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 722 ms / 2,000 ms |
コード長 | 6,627 bytes |
コンパイル時間 | 2,370 ms |
コンパイル使用メモリ | 81,772 KB |
実行使用メモリ | 105,208 KB |
最終ジャッジ日時 | 2024-10-12 19:42:59 |
合計ジャッジ時間 | 7,539 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.io.OutputStream;import java.io.PrintWriter;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.NoSuchElementException;public class Main {private static class Task {void solve(FastScanner in, PrintWriter out) {int N = in.nextInt();ArrayList<Integer>[] g = new ArrayList[N];for (int i = 0; i < N; i++) g[i] = new ArrayList<>();for (int i = 0; i < N - 1; i++) {int a = in.nextInt(), b = in.nextInt();g[a].add(b);g[b].add(a);}int[] U = in.nextIntArray(N);ArrayList<ArrayList<WeightedLCA.Edge>> graph = new ArrayList<>();for (int i = 0; i < N; i++) graph.add(new ArrayList<>());build(g, graph, U);WeightedLCA lca = new WeightedLCA(graph);long ans = 0;int Q = in.nextInt();for (; Q > 0; Q--) {int a = in.nextInt();int b = in.nextInt();long c = in.nextInt();int l = lca.getLCA(a, b);long dist = lca.getLength(a, b);dist = dist - U[l] + U[a] + U[b];ans += dist * c;}out.println(ans);}void build(ArrayList<Integer>[] g, ArrayList<ArrayList<WeightedLCA.Edge>> graph, int[] U) {ArrayDeque<Integer> deque = new ArrayDeque<>();boolean[] vis = new boolean[g.length];deque.addFirst(0);vis[0] = true;while (!deque.isEmpty()) {int v = deque.peekFirst();for (int u : g[v]) {if (vis[u]) continue;graph.get(v).add(new WeightedLCA.Edge(u, U[v]));graph.get(u).add(new WeightedLCA.Edge(v, U[v]));vis[u] = true;deque.addFirst(u);}if (deque.peekFirst() == v) deque.pollFirst();}}}static class WeightedLCA {static class Edge {long weight;int to;Edge(int to, long weight) {this.to = to;this.weight = weight;}}ArrayList<ArrayList<Edge>> G;int[][] parent;int[] depth;long[] dist;int root, logV;void build(int root) {Arrays.fill(depth, -1);ArrayDeque<Integer> stack = new ArrayDeque<>();stack.addFirst(root);parent[0][root] = -1;depth[root] = 0;dist[root] = 0;while (!stack.isEmpty()) {int v = stack.peekFirst();for (Edge e : G.get(v)) {int u = e.to;if (depth[u] >= 0) continue;parent[0][u] = v;depth[u] = depth[v] + 1;dist[u] = dist[v] + e.weight;stack.addFirst(u);}if (stack.peekFirst() == v) stack.pollFirst();}}WeightedLCA(final ArrayList<ArrayList<Edge>> adj) {int V = adj.size();root = 0;G = adj;dist = new long[V];depth = new int[V];logV = 1;for (int i = 1; i <= V; ) {i *= 2;logV++;}parent = new int[logV][V];build(root);for (int k = 0; k + 1 < logV; ++k)for (int v = 0; v < V; ++v)if (parent[k][v] < 0) {parent[k + 1][v] = -1;} else {parent[k + 1][v] = parent[k][parent[k][v]];}}int getLCA(int u, int v) {if (depth[u] > depth[v]) {int tu = u;u = v;v = tu;}for (int k = 0; k < logV; ++k) if (((depth[v] - depth[u]) >> k & 1) != 0) v = parent[k][v];if (u == v) return u;for (int k = logV - 1; k >= 0; --k)if (parent[k][u] != parent[k][v]) {u = parent[k][u];v = parent[k][v];}return parent[0][u];}long getLength(int u, int v) {int lca = getLCA(u, v);return dist[u] + dist[v] - dist[lca] * 2;}}// Templatepublic static void main(String[] args) {OutputStream outputStream = System.out;FastScanner in = new FastScanner();PrintWriter out = new PrintWriter(outputStream);Task solver = new Task();solver.solve(in, out);out.close();}private static class FastScanner {private final InputStream in = System.in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int bufferLength = 0;private boolean hasNextByte() {if (ptr < bufferLength) {return true;} else {ptr = 0;try {bufferLength = in.read(buffer);} catch (IOException e) {e.printStackTrace();}if (bufferLength <= 0) {return false;}}return true;}private int readByte() {if (hasNextByte()) return buffer[ptr++];else return -1;}private static boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}private void skipUnprintable() {while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}boolean hasNext() {skipUnprintable();return hasNextByte();}public String next() {if (!hasNext()) throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while (isPrintableChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}long nextLong() {if (!hasNext()) throw new NoSuchElementException();long n = 0;boolean minus = false;int b = readByte();if (b == '-') {minus = true;b = readByte();}if (b < '0' || '9' < b) {throw new NumberFormatException();}while (true) {if ('0' <= b && b <= '9') {n *= 10;n += b - '0';} else if (b == -1 || !isPrintableChar(b)) {return minus ? -n : n;} else {throw new NumberFormatException();}b = readByte();}}double nextDouble() {return Double.parseDouble(next());}double[] nextDoubleArray(int n) {double[] array = new double[n];for (int i = 0; i < n; i++) {array[i] = nextDouble();}return array;}double[][] nextDoubleMap(int n, int m) {double[][] map = new double[n][];for (int i = 0; i < n; i++) {map[i] = nextDoubleArray(m);}return map;}public int nextInt() {return (int) nextLong();}public int[] nextIntArray(int n) {int[] array = new int[n];for (int i = 0; i < n; i++) {array[i] = nextInt();}return array;}}}