結果

問題 No.1789 Tree Growing
ユーザー gew1fw
提出日時 2025-06-12 14:48:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 937 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 52,736 KB
最終ジャッジ日時 2025-06-12 14:52:18
合計ジャッジ時間 6,105 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 51 WA * 34
権限があれば一括ダウンロードができます

ソースコード

diff #

def count_leaves(adj, num_nodes):
    leaves = 0
    for i in range(1, num_nodes + 1):
        if len(adj[i]) == 1:
            leaves += 1
    return leaves

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0

    K = int(input[ptr])
    ptr += 1

    adj_t1 = [[] for _ in range(K + 1)]
    for _ in range(K - 1):
        a = int(input[ptr])
        b = int(input[ptr + 1])
        ptr += 2
        adj_t1[a].append(b)
        adj_t1[b].append(a)

    L_t1 = count_leaves(adj_t1, K)

    N = int(input[ptr])
    ptr += 1

    adj_t2 = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        c = int(input[ptr])
        d = int(input[ptr + 1])
        ptr += 2
        adj_t2[c].append(d)
        adj_t2[d].append(c)

    L_t2 = count_leaves(adj_t2, N)

    if L_t2 < L_t1:
        print(-1)
    else:
        max_red = (N - 1) - (L_t2 - L_t1)
        print(max_red)

if __name__ == "__main__":
    main()
0