ABC 148 F - Playing Tag on Tree

木の問題でした。

木の問題で意外と(個人的に)見落としがちなこと…

・　どの頂点を根にとってもいい場合がある。 ・　木の最短経路はO(|E|) = O(|V|)なので脳死で通る

あたり？他にもある気がする…

木の特殊系で考慮するのとして、

・うに(真ん中のノードから他の全てのノードに手が伸びてる)

が昔出てきた(ほかは覚えてない)

今回は、とにかく逃げるためには遠くに行くというのと木の最短経路探索を組み合わせれば解ける。

ただ、境界条件というか終わる時の条件がちょっとややこしかったのでそこらへんはちゃんと図を書かないときついかも。

とりあえず、

class tree:
    def __init__(self,n):
        self.edge = [set() for i in range(n)]
    def add_edge_dual(self,f,e):
        self.edge[f].add(e)
        self.edge[e].add(f)
    def add_edge_single(self,f,e):
        self.edge[f].add(e)
    def connected(self,node):
        return self.edge(node)


def dfs(graph,s):
    visited = [False for i in range(len(graph.edge))]
    distance = [-1 for i in range(len(visited))]
    visited[s] = True
    distance[s] = 0
    buf = [[s]]
    now = s
    while len(buf) != 0:
        nexts = buf[0]
        buf = buf[1:]
        temp = []
        for nex in nexts:
            for child in graph.edge[nex]:
                if visited[child] == False:
                    distance[child] = distance[nex]+1
                    temp.append(child)
                    visited[child] = True
                else:
                    continue
        if len(temp) == 0:
            continue
        else:
            buf.append(temp)
    return  distance

こんな感じに木とdfsを定義(後でライブラリ行き) して、

n,u,v = map(int,input().split())
t = tree(n)

for i in range(n-1):
    a,b = map(int,input().split())
    t.add_edge_dual(a-1,b-1)

taka = dfs(t,u-1)
aoki = dfs(t,v-1)

aofar = -1
for i in range(n):
    if taka[i] < aoki[i]:
        if aoki[i] > aofar:
            aofar = aoki[i]


print(aofar-1)

これ、手数に関わるのが、青木くんの到達手数なのに、高橋くんの到達手数で最も遠いところを求めてて何回かWAを出しました(ちゃんと条件を確認しよう!)