結果

問題 No.399 動的な領主
ユーザー GrenacheGrenache
提出日時 2016-07-16 11:59:08
言語 Java21
(openjdk 21)
結果
AC  
実行時間 940 ms / 2,000 ms
コード長 4,516 bytes
コンパイル時間 5,674 ms
コンパイル使用メモリ 80,380 KB
実行使用メモリ 79,128 KB
最終ジャッジ日時 2024-04-25 08:51:08
合計ジャッジ時間 14,661 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 48 ms
37,112 KB
testcase_01 AC 46 ms
37,104 KB
testcase_02 AC 49 ms
37,148 KB
testcase_03 AC 51 ms
37,232 KB
testcase_04 AC 104 ms
39,408 KB
testcase_05 AC 211 ms
49,280 KB
testcase_06 AC 886 ms
77,520 KB
testcase_07 AC 915 ms
75,004 KB
testcase_08 AC 912 ms
77,548 KB
testcase_09 AC 915 ms
77,520 KB
testcase_10 AC 121 ms
40,712 KB
testcase_11 AC 203 ms
48,276 KB
testcase_12 AC 804 ms
78,132 KB
testcase_13 AC 875 ms
79,128 KB
testcase_14 AC 653 ms
78,664 KB
testcase_15 AC 672 ms
78,796 KB
testcase_16 AC 676 ms
78,088 KB
testcase_17 AC 940 ms
77,712 KB
testcase_18 AC 911 ms
76,288 KB
権限があれば一括ダウンロードができます

ソースコード

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