Problem:


Problem I: Traffic Tree

Problem

  それぞれ1からNまでの番号が付いたN個の頂点が、N-1本の無向辺によって繋がれたグラフが与えられる。各頂点について、その頂点からスタートしてすべての頂点を訪れるための最短のステップ数を出力せよ。

  ただし、ある頂点から1本の辺をたどって別の頂点に移動することを1ステップとする。

Input

  入力は以下の形式で与えられる。

N
u1 v1
.
.
.
uN&minus;1 vN&minus;1

  1行目に、1つの整数Nが与えられる。

  続くN-1行のうちi行目にはi番目の辺の両端の頂点番号を表す整数ui, viが空白区切りで与えられる。

Constraints

  
2 ≤ N ≤ 105

  
1 ≤ ui,vi ≤ N (1 ≤ i ≤ N-1)

  
ui &ne; vi

  
与えられるグラフは連結である

Output

  頂点1から頂点Nについてi行目に頂点iからスタートしてすべての頂点を訪れるための最短のステップ数を出力せよ。

Sample Input 1

2
1 2

Sample Output 1

1
1

Sample Input 2

6
1 2
1 3
3 4
3 5
5 6

Sample Output 2

7
6
8
7
7
6

  

  Sample Input2の図



Sample input:
2
1 2


Sample output:
1
1

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)


def resolve():
    def dfs1(r_topo, par):
        for i in reversed(r_topo):
            stack = [i]
            while stack:
                idx = stack.pop()
                for to in G[idx]:
                    if to == par[i]:
                        continue
                    dist[idx] = max(dist[idx], dist[to] + 1)


    def dfs2(idx, d_par, par):
        stack = [(idx,d_par, par)]
        while stack:
            idx, d_par, par = stack.pop()
            d_child = []
            d_child.append((0, -1))
            for to in G[idx]:
                if to == par:
                    d_child.append((d_par + 1, to))
                else:
                    d_child.append((dist[to] + 1, to))
            d_child.sort(reverse=True)
            ans[idx] = d_child[0][0]
            for to in G[idx]:
                if to == par:
                    continue
                nx_d_par = d_child[d_child[0][1] == to][0]
                stack.append((to, nx_d_par, idx))
                #dfs2(to, nx_d_par, idx)

    N = int(input())
    if N == 1:
        return print(0)

    G = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)

    topo = []
    P = [-1] * N
    node = [0]
    while node:
        s = node.pop()
        topo.append(s)
        for to in G[s]:
            if to == P[s]:
                continue
            P[to] = s
            node.append(to)

    dist = [0]*N
    ans = [0] * N
    dfs1(topo,P)
    dfs2(0, 0, -1)
    for i in range(N):
        print((N - 1) * 2 - ans[i])


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append(y)
    edge[y].append(x)

topo = []
parent = [-1] * N
node = [0]
while node:
    s = node.pop()
    topo.append(s)
    for t in edge[s]:
        if t == parent[s]:
            continue
        parent[t] = s
        node.append(t)

memo = [0] * N  # ノードiより下の情報をマージしたもの
res = [0] * N  # 求めたいやつ、ノードiの上に出ていく情報
for s in reversed(topo):
    for t in edge[s]:
        if t == parent[s]:
            continue
        memo[s] = max(memo[s], res[t])
    res[s] = memo[s] + 1


TD = [0] * N  # 上からノードiへ向かう辺の情報
for s in topo:
    acc = TD[s]
    for t in edge[s]:
        if t == parent[s]:
            continue
        TD[t] = max(TD[t], acc)
        acc = max(acc, res[t])
    acc = 0
    for t in reversed(edge[s]):
        if t == parent[s]:
            continue
        TD[t] = max(TD[t], acc) + 1
        acc = max(acc, res[t])
        res[t] = max(memo[t], TD[t]) + 1


ans = [2 * (N - 1) - res[i] + 1 for i in range(N)]
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = deque([0])
T = []
while Q:
    i = deque.popleft(Q)
    T.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

BUA = [0] * N # Bottom Up : i以下をすべてまわる
BUB = [0] * N # Bottom Up : i以下をすべてまわってiに戻る
TDA = [0] * N # Top Down : iの上をすべてまわる
TDB = [0] * N # Top Down : iの上をすべてまわってiに戻る
for i in T[::-1]:
    if len(X[i]) == 0:
        BUA[i] = 0
        BUB[i] = 0
        continue
    s = 0
    ma = 0
    for j in X[i]:
        s += BUB[j] + 2
        ma = max(ma, BUB[j] - BUA[j] + 1)
    BUA[i] = s - ma
    BUB[i] = s

for i in T:
    B = [0] * (len(X[i]) + 1)
    C = [0] * (len(X[i]) + 1)
    for k, j in enumerate(X[i]):
        B[k+1] = B[k] + BUB[j] + 2
        C[k+1] = max(C[k], BUB[j] - BUA[j] + 2)
    s = 0
    ma = 0
    for k in range(len(X[i]))[::-1]:
        j = X[i][k]
        TDB[j] = TDB[i] + s + B[k] + 2
        TDA[j] = min(TDB[j] - max(ma, C[k]), TDA[i] + s + B[k] + 1)
        s += BUB[j] + 2
        ma = max(ma, BUB[j] - BUA[j] + 2)

for t in [min(a+d, b+c) for a, b, c, d in zip(BUA, BUB, TDA, TDB)]:
    print(t)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 9)
    
    from collections import deque

    N = int(input())

    #隣接リストの作成
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        G[u].append(v)
        G[v].append(u)

    #直径を求める
    dist = [-1] * N
    dist[0] = 0
    que = deque()
    que.append(0) #スタート地点を入れる
    while len(que) != 0:
        tmp = que.popleft()
        for i in G[tmp]:
            if dist[i] == -1:
                dist[i] = dist[tmp] + 1
                que.append(i)
    
    tmp = 0
    start = -1
    for index, x in enumerate(dist):
        if tmp < x:
            start = index
            tmp = x
    
    dist = [-1] * N
    dist[start] = 0
    que = deque()
    que.append(start) #スタート地点を入れる
    while len(que) != 0:
        tmp = que.popleft()
        for i in G[tmp]:
            if dist[i] == -1:
                dist[i] = dist[tmp] + 1
                que.append(i)

    tmp = 0
    gpal = -1
    for index, x in enumerate(dist):
        if tmp < x:
            goal = index
            tmp = x

    dist1 = [-1] * N
    dist1[goal] = 0
    que = deque()
    que.append(goal) #スタート地点を入れる
    while len(que) != 0:
        tmp = que.popleft()
        for i in G[tmp]:
            if dist1[i] == -1:
                dist1[i] = dist1[tmp] + 1
                que.append(i)

    # print (dist)
    # print (dist1)
    for i in range(N):
        print (2 * (N - 1) - max(dist[i], dist1[i]))

if __name__ == '__main__':
    main()