ABC394 - F - Alkane
問題
アルカンとは以下のような化合物。
code:ex.py
H H H
| | |
H-C-C-C-H
| | |
H H H
各頂点を条件を満たすように$ Cか$ Hに決めていくことを考える。
適当に根を決めて木DPをする。頂点$ iの親を$ p_iとする。 $ DP_i:=頂点$ iを根とする部分木であって、$ p_iとつなげばアルカンである（$ Cに$ 3個結合している）ものの最大サイズ
ただし便宜上$ Hひとつだけのグラフでも条件を満たすものとする。
根以外の頂点について
子が$ 3つ未満ならそれは$ Hにするしかない。
子が$ 3つならすべてつなげて$ p_iともつなげばアルカンになる。
子が$ 4つ以上なら、子からサイズの大きいものを$ 4つつなげることで$ p_iとつなぐより大きいアルカンになるかもしれない。
DPテーブルとは別に、その頂点での答えを計算する必要があることに注意。
code: f.py
from collections import deque
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
a, b = map(int, input().split())
a, b = a-1, b-1
ans = -1
for i in range(N):
ans = 0
if ans < 0:
print(ans)
exit()
P = -1 * N # Pi はiの親。iが根なら-1 Q = deque(0) # queue。根にするやつを最初に追加 R = [] # トポロジカルソート
while Q:
i = deque.popleft(Q)
R.append(i)
deque.append(Q, a)
continue
L = []
L.sort(reverse=True)
if len(L) >= 4:
elif i != 0:
print(max(ans))