結果

問題 No.1817 Reversed Edges
ユーザー merlinmerlin
提出日時 2022-01-21 22:20:00
言語 Java21
(openjdk 21)
結果
AC  
実行時間 637 ms / 2,000 ms
コード長 1,293 bytes
コンパイル時間 3,363 ms
コンパイル使用メモリ 91,636 KB
実行使用メモリ 82,884 KB
最終ジャッジ日時 2024-05-04 13:24:35
合計ジャッジ時間 13,162 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 62 ms
37,964 KB
testcase_01 AC 69 ms
37,828 KB
testcase_02 AC 62 ms
38,044 KB
testcase_03 AC 69 ms
37,796 KB
testcase_04 AC 60 ms
38,112 KB
testcase_05 AC 59 ms
37,960 KB
testcase_06 AC 70 ms
38,108 KB
testcase_07 AC 495 ms
62,088 KB
testcase_08 AC 312 ms
52,088 KB
testcase_09 AC 490 ms
60,160 KB
testcase_10 AC 324 ms
52,996 KB
testcase_11 AC 399 ms
54,516 KB
testcase_12 AC 627 ms
63,044 KB
testcase_13 AC 558 ms
63,332 KB
testcase_14 AC 637 ms
63,812 KB
testcase_15 AC 552 ms
63,284 KB
testcase_16 AC 547 ms
63,680 KB
testcase_17 AC 522 ms
64,756 KB
testcase_18 AC 547 ms
62,704 KB
testcase_19 AC 566 ms
63,280 KB
testcase_20 AC 569 ms
64,012 KB
testcase_21 AC 529 ms
63,324 KB
testcase_22 AC 428 ms
62,592 KB
testcase_23 AC 455 ms
62,952 KB
testcase_24 AC 458 ms
82,884 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        int n=Integer.parseInt(bu.readLine());
        int i,c[]=new int[n],e[]=new int[n];
        ArrayList<Integer> g[]=new ArrayList[n];

        for(i=0;i<n;i++) g[i]=new ArrayList<>();
        for(i=0;i<n-1;i++)
        {
            String s[]=bu.readLine().split(" ");
            int u=Integer.parseInt(s[0])-1,v=Integer.parseInt(s[1])-1;
            g[u].add(v);
            g[v].add(u);
        }

        dfs(g,c,0,-1);
        reroot(g,c,e,0,-1);
        for(i=0;i<n;i++) sb.append(c[i]+e[i]+"\n");
        System.out.print(sb);
    }

    static void dfs(ArrayList<Integer> g[],int c[],int n,int p)
    {
        for(int x:g[n])
        if(x!=p)
        {
            dfs(g,c,x,n);
            c[n]+=c[x];
            if(x<n) c[n]++;
        }
    }

    static void reroot(ArrayList<Integer> g[],int c[],int e[],int n,int p)
    {
        for(int x:g[n])
        if(x!=p)
        {
            e[x]=e[n];
            e[x]+=c[n]-c[x];
            if(n>x) e[x]--;
            else e[x]++;
            reroot(g,c,e,x,n);
        }
    }
}
0