Euler tour

木の隣接する頂点をrootから辿っていき、全ての頂点を通る経路を求める。
葉以外の頂点は2回以上通ることとなる。

from collections import defaultdict, deque, Counter


def euler_tour(G, root=0):
    n = len(G)
    euler = []
    dq = deque([root])
    dq2 = deque()
    visited = [0] * n
    while dq:
        u = dq.pop()
        euler += [u]
        if visited[u]:
            continue
        for v in G[u]:
            if visited[v]:
                dq += [v]
            # [親頂点、子頂点、子頂点、。。。]と入れていく.その後連結
            else:
                dq2 += [v]
        dq.extend(dq2)
        dq2 = deque()
        visited[u] = 1
    return euler

colorful tree
https://atcoder.jp/contests/abc133/submissions/9015885
クエリ先読み、lcaなども含まれる盛りだくさんな問題。