結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
![]() |
提出日時 | 2019-08-18 19:25:32 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 528 ms / 2,000 ms |
コード長 | 869 bytes |
コンパイル時間 | 156 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 66,660 KB |
最終ジャッジ日時 | 2024-10-01 14:10:46 |
合計ジャッジ時間 | 9,362 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
from collections import defaultdictimport sysinput = sys.stdin.readlinesys.setrecursionlimit(10 ** 6)def dfs(cur, prev, state):if memo[cur][state] != -1:return memo[cur][state]if state == 0:res = 0for child in adj_dict[cur]:if prev != child:res += max(dfs(child, cur, 0), dfs(child, cur, 1))else:res = 1for child in adj_dict[cur]:if prev != child:res += max(dfs(child, cur, 0), dfs(child, cur, 1) - 1)memo[cur][state] = resreturn resN = int(input())adj_dict = defaultdict(list)for _ in range(N-1):Ui, Vi = map(int, input().split())adj_dict[Ui-1].append(Vi-1)adj_dict[Vi-1].append(Ui-1)memo = [[-1, -1] for _ in range(N)]ans = max(dfs(0, None, 0), dfs(0, None, 1))print(ans)