結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
![]() |
提出日時 | 2020-02-04 09:51:35 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 410 ms / 2,000 ms |
コード長 | 693 bytes |
コンパイル時間 | 110 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 38,060 KB |
最終ジャッジ日時 | 2024-09-20 06:59:47 |
合計ジャッジ時間 | 7,511 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesN = int(readline())m = map(int, read().split())UV = zip(m,m)graph = [[] for _ in range(N+1)]for u,v in UV:graph[u].append(v)graph[v].append(u)root = 1parent = [0] * (N+1)order = []stack = [root]while stack:x = stack.pop()order.append(x)for y in graph[x]:if y == parent[x]:continueparent[y] = xstack.append(y)dp_0 = [0] * (N+1)dp_1 = [1] * (N+1)for v in order[::-1]:p = parent[v]dp_0[p] += max(dp_0[v], dp_1[v])dp_1[p] += dp_0[v]answer = max(dp_0[root], dp_1[root])print(answer)