ABC385Eを解いた【ユ木】

筆者はレート800前後の茶～緑コーダ

ABC385当日にACできなかったE問題を解いていく

実装コード

中心をu, その周辺の x 点の頂点を v とする
uは1からNまで全探索、
xは1からuについてる頂点数まで探索、
yは v の中で一番小さい頂点数になるようだ

yを求めるために、頂点v についている辺の数を降順にソートする。
どのようにやるの？と思うがsortのkeyに関数を定義するようだ。
(個人的にはこのテクニックがこの問題一番の学び)

T[u].sort(key=lambda v: -d[v])

求める値である除外する頂点の数はユ木にならなかった頂点の数で、ユ木の頂点は1+x+xyと求められる。Nからユ木の頂点数を引いた数が削除する頂点数で、あとはminで最小値を更新すればOK

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from itertools import product, accumulate, groupby
from sortedcontainers import SortedList
import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)


def main():
    N = rI()
    T = defaultdict(list)
    d = defaultdict(lambda: 0)
    for _ in range(N-1):
        u,v = rLI()
        T[u].append(v)
        T[v].append(u)
        d[u] += 1
        d[v] += 1
    ans = N
    for u in range(1,N+1):
        T[u].sort(key=lambda v: -d[v])
        x=y=0
        # err(u, T[u])
        # err({v:d[v] for v in T[u]})
        for v in T[u]:
            x += 1
            y = d[v] - 1
            ret = N-(1+x+x*y)
            # err(f"{ans=}, {x=}, {y=}, {ret=}")
            ans = min(ans,ret)
    print(ans)
    
    
if __name__ == '__main__':
    main()

まとめ

ABC当日は木が見えた時点で即解くのを諦めてしまったが、
公式解説を読みつつ、この記事を書いたら、
少し理解できたような気がする。

苦手な問題でもこのようなアウトプットをして、
理解度を高めていきたい。