結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
![]() |
提出日時 | 2021-04-25 00:32:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,374 ms / 2,000 ms |
コード長 | 1,071 bytes |
コンパイル時間 | 308 ms |
コンパイル使用メモリ | 82,524 KB |
実行使用メモリ | 363,776 KB |
最終ジャッジ日時 | 2024-07-04 09:16:47 |
合計ジャッジ時間 | 15,135 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
import sysfrom functools import lru_cachesys.setrecursionlimit(10**7)def I(): return int(sys.stdin.readline().rstrip())def MI(): return map(int,sys.stdin.readline().rstrip().split())def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))def LI2(): return list(map(int,sys.stdin.readline().rstrip()))def S(): return sys.stdin.readline().rstrip()def LS(): return list(sys.stdin.readline().rstrip().split())def LS2(): return list(sys.stdin.readline().rstrip())N = I()Graph = [[] for _ in range(N)]for _ in range(N-1):u,v = MI()u -= 1v -= 1Graph[u].append(v)Graph[v].append(u)@lru_cache(maxsize=None)def dfs(i,par,r):res = 0if len(Graph[i]) == 1 and par == Graph[i][0]:if not r:res = 1else:if not r:res += 1for j in Graph[i]:if j != par:if r:res += max(dfs(j,i,0),dfs(j,i,1))else:res += dfs(j,i,1)return resans = max(dfs(0,-1,0),dfs(0,-1,1))print(ans)