結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
![]() |
提出日時 | 2019-05-04 23:35:54 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,499 bytes |
コンパイル時間 | 200 ms |
コンパイル使用メモリ | 13,056 KB |
実行使用メモリ | 70,908 KB |
最終ジャッジ日時 | 2024-06-23 12:17:45 |
合計ジャッジ時間 | 40,077 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 11 TLE * 10 |
ソースコード
import numpy as npclass sol(object):def __init__(self, N, tree):self.N = Nself.tree = treeself.dp0 = np.array([0] * N, dtype=int)self.dp1 = np.array([0] * N, dtype=int)self.visit_cnt = [0] * Nself.parent = np.array([-1] * N, dtype=int)def dns(self, cur):h = []h.append(cur)childs = [[] for i in range(self.N)]while len(h) > 0:v = h.pop()self.visit_cnt[v] += 1if len(self.tree[v]) == 0:self.dp0[v] = 1self.dp1[v] = 0elif self.visit_cnt[v] -1 < len(self.tree[v]):child = self.tree[v][self.visit_cnt[v] -1]if child != self.parent[v]:h.append(v)h.append(child)childs[v].append(child)self.parent[child] = velse:h.append(v)else:self.dp1[v] = sum([max(t) for t in zip(self.dp0[childs[v]], self.dp1[childs[v]])])self.dp0[v] = 1 + sum([max(t[0] -1, t[1]) for t in zip(self.dp0[childs[v]], self.dp1[childs[v]])])returndef ans(self):self.dns(0)return max(self.dp0[0],self.dp1[0])N=int(input())tree = [[] for i in range(N)]for i in range(N -1):e = list(map(int, input().split()))tree[e[0] -1].append(e[1] -1)tree[e[1] -1].append(e[0] -1)print(sol(N, tree).ans())