結果
問題 | No.2677 Minmax Independent Set |
ユーザー |
|
提出日時 | 2023-12-01 01:37:28 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,323 bytes |
コンパイル時間 | 302 ms |
コンパイル使用メモリ | 82,384 KB |
実行使用メモリ | 435,396 KB |
最終ジャッジ日時 | 2024-09-30 00:06:36 |
合計ジャッジ時間 | 17,451 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 7 TLE * 3 -- * 51 |
ソースコード
#!/usr/bin/python3import syssys.setrecursionlimit(10**6)def main():N = int(input())to = [[] for i in range(N)]for i in range(N-1):x, y = map(int, input().split())x -= 1y -= 1to[x].append(y)to[y].append(x)# https://snuke.hatenablog.com/entry/2019/01/16/203626 を改変pi = [0] * Ndeg = [0] * Ndp = [[] for i in range(N)]ans = [0] * Ndef dfs(v, p=-1):deg[v] = len(to[v])res = (0, 0)dp[v] = [0]*deg[v]for i in range(deg[v]):u = to[v][i]if u == p:pi[v] = icontinuedp[v][i] = dfs(u, v)val = (max(dp[v][i]), dp[v][i][0])res = (res[0] + val[0], res[1] + val[1])return (res[0], res[1] + 1)def bfs(v, res_p=0, p=-1):if p != -1:dp[v][pi[v]] = res_pdpl = [(0, 0)]*(deg[v]+1)for i in range(deg[v]):dpl[i+1] = (dpl[i][0] + max(dp[v][i]), dpl[i][1] + dp[v][i][0])dpr = [(0, 0)]*(deg[v]+1)for i in range(deg[v]-1,-1,-1):dpr[i] = (dpr[i+1][0] + max(dp[v][i]), dpr[i+1][1] + dp[v][i][0])ans[v] = (dpr[0][0], dpr[0][1] + 1)for i in range(deg[v]):u = to[v][i]if u == p:continueval = (dpl[i][0] + dpr[i+1][0], dpl[i][1] + dpr[i+1][1] + 1)bfs(u, val, v)dfs(0)bfs(0)# 答え出力print(min([x[1] for x in ans]))main()