halcの競プロ精進ブログ

はるくが競プロしたことを書き留めるなにか

【今日の精進】ARC156C - Tree and LCS

競プロ 今日の精進 ARC 黄Diff

毎日格上の問題を倒すやつの36日目です。

問題リンク

atcoder.jp

問題概要

木が与えられるよ。

すべてのパス (x_1,x_2,\dots x_k) について、(x_1,x_2,\dots x_k) と (P_{x_1},P_{x_2},\dots P_{x_k}) のLCAの最大値を類似度として、これを最小にする順列 P を構築してね。

解法

明らかに、類似度を0にすることは不可能です。*1

そのため、類似度を1にすることを考えます。

パスグラフの場合、頂点の番号と逆向きに番号を振りたくなります。これを一般の場合にも応用します。

何がしたいかというと、「頂点の番号と遠いところに数字を書きたい」のです。この考え方をすると、以下のアルゴリズムに行きつきます。

  • すべての葉に対して、番号をシャッフルしてつけたのち、葉を削除する*2

このようにしてうまくいくことは、帰納法により示せます。

提出コード

from collections import deque

N=int(input())
tree=[set() for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    tree[a-1].add(b-1)
    tree[b-1].add(a-1)
one=deque()
for i in range(N):
    if len(tree[i])==1:
        one.append((0,i))
cnt=0
ans=[-1]*N
while len(one)>0:
    now=[]
    while len(one)>0 and one[0][0]==cnt:
        _,pos=one.popleft()
        for i in tree[pos]:
            tree[i].discard(pos)
            if len(tree[i])==1:
                one.append((cnt+1,i))
        now.append(pos)
    for i in range(len(now)):
        ans[now[i]]=now[i-1]+1
    cnt+=1
print(*ans)

Submission #46932286 - AtCoder Regular Contest 156

感想

nok0さんにいただいたけどおもしろかった

*1:どの2頂点の間にもパスが存在するため

*2:1頂点の場合以外、同じ場所に書かないように