結果

問題 No.399 動的な領主
コンテスト
ユーザー Grenache
提出日時 2016-07-16 11:59:08
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,141 ms / 2,000 ms
コード長 4,516 bytes
コンパイル時間 6,026 ms
コンパイル使用メモリ 79,680 KB
実行使用メモリ 78,504 KB
最終ジャッジ日時 2024-11-07 19:20:41
合計ジャッジ時間 19,110 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

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


public class Main_yukicoder399 {

    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 u = sc.nextInt() - 1;
			int v = sc.nextInt() - 1;
			edges.get(u).add(v);
			edges.get(v).add(u);
		}

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

		long[] sum = new long[n];
		int q = sc.nextInt();
		for (int i = 0; i < q; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;

			int lcav = lca.getLCA(a, b);
			sum[a] += 1;
			sum[b] += 1;
			sum[lcav] -= 1;
			if (lca.parent[0][lcav] != -1) {
				sum[lca.parent[0][lcav]] -= 1;
			}
		}

		long ret = 0;
		boolean[] used = new boolean[n];
		Deque<Integer> st = new ArrayDeque<>();
		st.push(root);
		while (!st.isEmpty()) {
			int e = st.peek();
			int pe = lca.parent[0][e];

			if (!used[e]) {
				for (int ne : edges.get(e)) {
					if (ne == pe) {
						continue;
					}
					st.push(ne);
				}
				used[e] = true;
			} else {
				for (int ne : edges.get(e)) {
					if (ne == pe) {
						continue;
					}
					sum[e] += sum[ne];
				}
				st.pop();
				ret += sum[e] * (sum[e] + 1) / 2;
			}
		}

		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);
		}
	}
}
0