結果
問題 | No.1098 LCAs |
ユーザー |
![]() |
提出日時 | 2020-06-26 22:20:26 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,770 ms / 2,000 ms |
コード長 | 3,790 bytes |
コンパイル時間 | 2,563 ms |
コンパイル使用メモリ | 89,200 KB |
実行使用メモリ | 109,272 KB |
最終ジャッジ日時 | 2024-07-04 22:02:41 |
合計ジャッジ時間 | 15,673 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.ArrayList;import java.util.Arrays;import java.util.InputMismatchException;import java.util.NoSuchElementException;public class Main {static PrintWriter out;static InputReader ir;static void solve() {int n = ir.nextInt();Graph[] g = new Graph[n];for (int i = 0; i < n; i++)g[i] = new Graph();for (int i = 0; i < n - 1; i++) {int u = ir.nextInt() - 1;int v = ir.nextInt() - 1;g[u].add(v);g[v].add(u);}long[] dp = new long[n];dfs(0, -1, g, dp);for (int i = 0; i < n; i++) {long res = 0;for (int to : g[i]) {if (dp[to] < dp[i]) {res += (dp[i] - dp[to] - 1) * dp[to];}}out.println(res + dp[i] * 2 - 1);}}static long dfs(int cur, int par, Graph[] g, long[] dp) {dp[cur] = 1;for (int to : g[cur]) {if (to != par) {dp[cur] += dfs(to, cur, g, dp);}}return dp[cur];}static class Graph extends ArrayList<Integer> {}public static void main(String[] args) {ir = new InputReader(System.in);out = new PrintWriter(System.out);solve();out.flush();}static class InputReader {private InputStream in;private byte[] buffer = new byte[1024];private int curbuf;private int lenbuf;public InputReader(InputStream in) {this.in = in;this.curbuf = this.lenbuf = 0;}public boolean hasNextByte() {if (curbuf >= lenbuf) {curbuf = 0;try {lenbuf = in.read(buffer);} catch (IOException e) {throw new InputMismatchException();}if (lenbuf <= 0)return false;}return true;}private int readByte() {if (hasNextByte())return buffer[curbuf++];elsereturn -1;}private boolean isSpaceChar(int c) {return !(c >= 33 && c <= 126);}private void skip() {while (hasNextByte() && isSpaceChar(buffer[curbuf]))curbuf++;}public boolean hasNext() {skip();return hasNextByte();}public String next() {if (!hasNext())throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while (!isSpaceChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public int nextInt() {if (!hasNext())throw new NoSuchElementException();int c = readByte();while (isSpaceChar(c))c = readByte();boolean minus = false;if (c == '-') {minus = true;c = readByte();}int res = 0;do {if (c < '0' || c > '9')throw new InputMismatchException();res = res * 10 + c - '0';c = readByte();} while (!isSpaceChar(c));return (minus) ? -res : res;}public long nextLong() {if (!hasNext())throw new NoSuchElementException();int c = readByte();while (isSpaceChar(c))c = readByte();boolean minus = false;if (c == '-') {minus = true;c = readByte();}long res = 0;do {if (c < '0' || c > '9')throw new InputMismatchException();res = res * 10 + c - '0';c = readByte();} while (!isSpaceChar(c));return (minus) ? -res : res;}public double nextDouble() {return Double.parseDouble(next());}public int[] nextIntArray(int n) {int[] a = new int[n];for (int i = 0; i < n; i++)a[i] = nextInt();return a;}public long[] nextLongArray(int n) {long[] a = new long[n];for (int i = 0; i < n; i++)a[i] = nextLong();return a;}public char[][] nextCharMap(int n, int m) {char[][] map = new char[n][m];for (int i = 0; i < n; i++)map[i] = next().toCharArray();return map;}}static void tr(Object... o) {System.err.println(Arrays.deepToString(o));}}