Problem:


Score : 1200 points

Problem Statement

Takahashi's office has N rooms. Each room has an ID from 1 to N.
There are also N-1 corridors, and the i-th corridor connects Room a_i and Room b_i.
It is known that we can travel between any two rooms using only these corridors.

Takahashi has got lost in one of the rooms. Let this room be r.
He decides to get back to his room, Room 1, by repeatedly traveling in the following manner:

Travel to the room with the smallest ID among the rooms that are adjacent to the rooms already visited, but not visited yet.

Let c_r be the number of travels required to get back to Room 1.
Find all of c_2,c_3,...,c_N.
Note that, no matter how many corridors he passes through in a travel, it still counts as one travel.

Constraints

2 \leq N \leq 2\times 10^5

1 \leq a_i,b_i \leq N

a_i \neq b_i

The graph given as input is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}

Output

Print c_r for each r, in the following format:

c_2 c_3 ... c_N

Sample Input 1

6
1 5
5 6
6 2
6 3
6 4

Sample Output 1

5 5 5 1 5

For example, if Takahashi was lost in Room 2, he will travel as follows:

Travel to Room 6.

Travel to Room 3.

Travel to Room 4.

Travel to Room 5.

Travel to Room 1.

Sample Input 2

6
1 2
2 3
3 4
4 5
5 6

Sample Output 2

1 2 3 4 5

Sample Input 3

10
1 5
5 6
6 10
6 4
10 3
10 8
8 2
4 7
4 9

Sample Output 3

7 5 3 1 3 4 7 4 5



Sample input:
6
1 5
5 6
6 2
6 3
6 4


Sample output:
5 5 5 1 5

Submission status: Wrong Answer

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc029/tasks/agc029_e
1に近いところから決めていくのが良いか？
または部屋1を根とした木を考える？
部屋1スタートなら答えは0
部屋1に隣接している部屋なら答えは0

1を原点としてそこから定めていくとする
移動回数確定点に隣接する点を1つ取ってくる(Xとする)
Xに隣接する確定点をAとする。ここで、(X > Aは確定)
Xから探索する。また、Aにたどり着きさえすれば、後はAから原点までの移動回数で移動可能？
→これは正しい。(途中でXより大きい点を通ることは無いため)

Xから隣接点を探索していき、Aがでるまで小さい点を訪問し続ける？
それまで訪問した点は、すべて同じ時間になる？
→正しそう
(部分木で、A超をまたがないといけない点以外は何処から始めても全て訪問する羽目になる)
(また、最終的にはAにたどり着くから)

そんなかんたんでいいのか？？

→WA…

可能性1: 考察がだめ
可能性2: コードがだめ

取るボーダーAは、1とのパス上にある最大の点じゃん！
→つまり,前のst

1-4-2-5-3
は
0 2 4 1 4になるはず
→ 2 4 1 3 になってる

親と閾値は別！
閾値は今まで出たstの内最大の物
"""

from collections import deque
N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    lis[a].append(b)
    lis[b].append(a)

dis = [float("inf")] * N
unvisit = [True] * N
unvisit[0] = False
dis[0] = 0

stpb = deque([])

for nex in lis[0]:
    stpb.append([nex,0,0])

while len(stpb) > 0:

    st,par,bord = stpb.popleft()

    q = deque([st])
    nvs = [st]

    while len(q) > 0:

        now = q.popleft()

        for nex in lis[now]:

            if unvisit[nex]:

                if nex > bord:
                    stpb.append([nex,now,max(bord,st)])

                elif nex < bord:
                    q.append(nex)
                    nvs.append(nex)

            unvisit[nex] = False

    for i in nvs:
        dis[i] = dis[par] + len(nvs)

print (*dis[1:])

Submission status: Wrong Answer

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc029/tasks/agc029_e
1に近いところから決めていくのが良いか？
または部屋1を根とした木を考える？
部屋1スタートなら答えは0
部屋1に隣接している部屋なら答えは0

1を原点としてそこから定めていくとする
移動回数確定点に隣接する点を1つ取ってくる(Xとする)
Xに隣接する確定点をAとする。ここで、(X > Aは確定)
Xから探索する。また、Aにたどり着きさえすれば、後はAから原点までの移動回数で移動可能？
→これは正しい。(途中でXより大きい点を通ることは無いため)

Xから隣接点を探索していき、Aがでるまで小さい点を訪問し続ける？
それまで訪問した点は、すべて同じ時間になる？
→正しそう
(部分木で、A超をまたがないといけない点以外は何処から始めても全て訪問する羽目になる)
(また、最終的にはAにたどり着くから)

そんなかんたんでいいのか？？

"""

from collections import deque
N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    lis[a].append(b)
    lis[b].append(a)

dis = [float("inf")] * N
unvisit = [True] * N
unvisit[0] = False
dis[0] = 0

stq = deque([])

for nex in lis[0]:
    stq.append([nex,0])

while len(stq) > 0:

    st,A = stq.popleft()
    nv = [st]

    q = deque([st])

    while len(q) > 0:

        now = q.popleft()

        for nex in lis[now]:

            if unvisit[nex]:
                if nex > A:
                    stq.append([nex,now])
                elif nex < A:
                    nv.append(nex)
                    q.append(nex)

            unvisit[nex] = False

    for i in nv:
        dis[i] = len(nv) + dis[A]

print (*dis[1:])

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

highest_v = [0] * (N+1) # 親側（自身は含まない）の最大番号の頂点
for x in order[1:]:
    p = parent[x]
    h = highest_v[p]
    if p < h:
        highest_v[x] = h
    else:
        highest_v[x] = p

root = list(range(N+1)) # 連結成分の最も根側
size = [1] * (N+1)
for x in order[1:]:
    p = parent[x]
    if highest_v[p] < x:
        continue
    r = root[p]
    root[x] = r
    size[r] += 1

dp = [0] * (N+1)
for x in order[1:]:
    p = parent[x]
    if root[x] == x:
        dp[x] = dp[p] + size[x]
    else:
        dp[x] = dp[p]

print(' '.join(map(str,dp[2:])))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from collections import defaultdict, deque
from heapq import heappush, heappop, heapreplace

def solve():
    N = int(input())
    V = list(range(1, N+1))
    E = defaultdict(set)
    for _ in range(N-1):
        a, b =  map(int,input().split())
        E[a].add(b)
        E[b].add(a)
    Q = [1]
    while Q:
        r = heappop(Q)
        for s in E[r]:
            E[s].discard(r)
            heappush(Q, s)
    #print(E)

    Q = [1]
    while Q:
        r = heappop(Q)
        R = E[r].copy()
        while R:
            s = R.pop()
            P = E[s].copy()
            s_ = {s} if isinstance(s,int) else set(s)
            while P:
                t = P.pop()
                if t < (r if isinstance(r,int) else max(r)):
                    s_.add(t)
                    for u in E[t]:
                        P.add(u)
            s__ = tuple(s_)
            E[s__] = set(u for t in s_ for u in E.pop(t,{}))-s_
            E[r].discard(s)
            E[r].add(s__) 
            heappush(Q, s__)
    #print(E)
    E = dict(E)
    C = defaultdict(int)
    Q = [1]
    while Q:
        r = heappop(Q)
        for s in E.get(r):
            C[s] = C[r] + (1 if isinstance(r,int) else len(s))
            heappush(Q, s)
    #print(C)
    D = [0 for _ in range(N-1)]
    for key in C:
        if isinstance(key, tuple):
            for i in key:
                D[i-2] = C[key]
    #print(D)
    res = ' '.join([str(d) for d in D])

    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
result=''
R=list(list(map(int,input().split())) for i in range(N-1))

for k in range(2,N+1):
    keyset=[]
    for i in range(N):
        keyset.append([])
    
    for i in range(N-1):
        keyset[R[i][0]-1].append(R[i][1])
        keyset[R[i][1]-1].append(R[i][0])
        
    stock=[]
    count=0
    m=k    
    
    for i in range(N-1):
        for j in range(len(keyset)):
            if m in keyset[j]:
                keyset[j].remove(m)

        for j in range(len(keyset[m-1])):
            stock.append(keyset[m-1][j])
        m=min(stock)
        stock.remove(m)
        count+=1
        #print(k,i,m,count) 
        if m==1:
            result+=str(count)+' '
            #print('break')
            break
print(result[:-1])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
result=''
R=list(list(map(int,input().split())) for i in range(N-1))

for k in range(2,N+1):
    keyset=[]
    for i in range(N):
        keyset.append([])
    
    for i in range(N-1):
        keyset[R[i][0]-1].append(R[i][1])
        keyset[R[i][1]-1].append(R[i][0])
        
    stock=[]
    count=0
    m=k    
    
    for i in range(N-1):
        for j in range(len(keyset)):
            if m in keyset[j]:
                keyset[j].remove(m)

        for j in range(len(keyset[m-1])):
            stock.append(keyset[m-1][j])
        m=min(stock)
        stock.remove(m)
        count+=1
        #print(k,i,m,count) 
        if m==1:
            result+=str(count)+' '
            #print('break')
            break
print(result[:-1])

Submission status: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc029/tasks/agc029_e
1に近いところから決めていくのが良いか？
または部屋1を根とした木を考える？
部屋1スタートなら答えは0
部屋1に隣接している部屋なら答えは0

1を原点としてそこから定めていくとする
移動回数確定点に隣接する点を1つ取ってくる(Xとする)
Xに隣接する確定点をAとする。ここで、(X > Aは確定)
Xから探索する。また、Aにたどり着きさえすれば、後はAから原点までの移動回数で移動可能？
→これは正しい。(途中でXより大きい点を通ることは無いため)

Xから隣接点を探索していき、Aがでるまで小さい点を訪問し続ける？
それまで訪問した点は、すべて同じ時間になる？
→正しそう
(部分木で、A超をまたがないといけない点以外は何処から始めても全て訪問する羽目になる)
(また、最終的にはAにたどり着くから)

そんなかんたんでいいのか？？

→WA…

可能性1: 考察がだめ
可能性2: コードがだめ

取るボーダーAは、1とのパス上にある最大の点じゃん！
→つまり,前のst

1-4-2-5-3
は
0 2 4 1 4になるはず
→ 2 4 1 3 になってる

親と閾値は別！
閾値は今まで出たstの内最大の物

え～～～～～～～～～
1個増えただけかよぉぉぉぉぉぉ

ちゃんと証明して考えよう…
スタート地点だけ別で考えるっぽい？
→スタート地点の場合だけ閾値が違う

他の点の閾値は max(st,bord)
スタート地点は,bordだけ見る
1-4-6-3-2
      |
      5
は、6の閾値は4
3,2,5は6となる

大→小のつながりに注目
小A→大→小B

蛇口を始点に下ろして水をためていくイメージで考えると楽
根に近いこと頃から決めていく
根から昇順になるように「スタート地点」を決める
(これはdfsをして今まで出て来たより大きい点が出てきたらそうすればよい)
スタート地点より下流は、スタート地点より小さい点を全部取らないと先に進めない

つまり、bfsをしてあげればよい(基準点はスタート地点)

スタート地点の答えは、今書いてるdfsでおｋ
そうでない点は、スタート地点から派生の部分木を考えて、
stの親の答え +1+ 自分の属す部分木のスタート地点以下の高さの点　＋　Σそうでない部分木のstの1つ前のスタート地点の高さ以下の点

stは, stの親の答え+1+Σ部分木のstの1つ前のスタート地点の高さ以下の点
となる

コードはまずstを探索。浅い方から再びdfsをしていく
同じ点は高々3回しか調べないので O(N)
"""

import sys
sys.setrecursionlimit(300000)
from collections import deque
N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    lis[a].append(b)
    lis[b].append(a)

dis = [float("inf")] * N
dis[0] = 0

stlis = []
last_st = [0] * N
plis = [i for i in range(N)]

def get_st(v,p,nmax):

    plis[v] = p
    last_st[v] = nmax
    if v > nmax:
        stlis.append(v)
    for nex in lis[v]:
        if nex != p:
            get_st(nex,v,max(nmax,v))
    return

get_st(0,0,0)

#print (stlis)
#print (last_st)

def dfs(v,p,bord,mode):

    if v > bord:
        return 0

    ret = 1
    if mode == 1:
        ctree_vs[-1].append(v)
    for nex in lis[v]:
        if nex != p:
            ret += dfs(nex,v,bord,mode)
    return ret
    
        

for st in stlis:

    #全て子部分木にたいして必要な情報収集をする
    #どの子部分木にどの頂点が含まれてるか & bordがstの頂点数 & bordが last_st[st]のときに超点数

    ctree_vs = []
    on_st = []
    on_lb = []

    for nex in lis[st]:
        if nex != plis[st]:
            ctree_vs.append([])
            on_st.append( dfs(nex,st,st,1) )
            on_lb.append( dfs(nex,st,last_st[st] , 0))

    lbsum = sum(on_lb)
    for i in range(len(ctree_vs)):
        for v in ctree_vs[i]:
            dis[v] = dis[plis[st]] + 1 + lbsum - on_lb[i] + on_st[i]

    dis[st] = dis[plis[st]] + 1 + lbsum

print (*dis[1:])
            


#WAコード
"""
from collections import deque
N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    lis[a].append(b)
    lis[b].append(a)

dis = [float("inf")] * N
unvisit = [True] * N
unvisit[0] = False
dis[0] = 0

stpb = deque([])

for nex in lis[0]:
    stpb.append([nex,0,0])

def dfs(v,p,bord):
    ret = 1
    for nex in lis[v]:
        if nex != p and nex < bord:
            ret += dfs(nex,v,bord)

    #print (v+1,p+1,bord+1,ret)
    return ret

while len(stpb) > 0:

    st,par,bord = stpb.popleft()
    #print (st+1,par+1,bord+1)

    q = deque([st])
    nvs = []

    if st != 0:
        dis[st] = dis[par] + dfs(st,par,bord)
    #print (dis)

    while len(q) > 0:

        now = q.popleft()
        unvisit[now] = False

        for nex in lis[now]:

            if unvisit[nex]:

                if nex > max(bord,st):
                    stpb.append([nex,now,max(bord,st)])

                elif nex < max(bord,st):
                    q.append(nex)
                    nvs.append(nex)

    for i in nvs:
        dis[i] = dis[par] + (len(nvs)+1)

    
print (*dis[1:])
"""

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
p=[]
list=[[]for i in range(N-1)]
for i in range(N-1):
    p=input().split()
    for char in p:
        list[i].append(int(char))
graph=[[] for i in range(N+1)]
for l in list:
    graph[l[0]].append(l[1])
    graph[l[1]].append(l[0])
count=[]
graph_c=[0 for i in range(0,N+4)]
for p in range(2,N+1):
    if graph_c[p]==0:
        c=1
        buf=[[],[]]
        done_point=[]
        done_list=[]
        done_point.append(p)
        done_list+=graph[p]
        m=min(graph[p])
        while m != 1 and graph_c[m]==0:
            if len(graph[m])>=3:
                buf[0].append(m)
                buf[1].append(c)
            c=c+1
            done_point.append(m)
            done_list+=graph[m]
            for a in done_point:
                if a in done_list:
                    done_list.remove(a)
            m=min(done_list)
        if not buf:
            b=buf[0][0]
            if graph_c[b]==0:
                count.append(graph_c[b])
        if m==1:
            if not buf:
                graph_c[b]=c-buf[1][0]+1
            count.append(c)
    else:
        count.append(graph_c[p])
for x in count:
    print(x, end=" ")
print("")

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
p=[]
list=[[]for i in range(N-1)]
for i in range(N-1):
    p=input().split()
    for char in p:
        list[i].append(int(char))
graph=[[] for i in range(N+1)]
for l in list:
    graph[l[0]].append(l[1])
    graph[l[1]].append(l[0])
count=[]
for p in range(2,N+1):
    c=1
    done_point=[]
    done_list=[]
    done_point.append(p)
    done_list+=graph[p]
    m=min(graph[p])
    while m != 1:
        c=c+1
        done_point.append(m)
        done_list+=graph[m]
        for a in done_point:
            if a in done_list:
                done_list.remove(a)
        m=min(done_list)
    count.append(c)
for x in count:
    print(x, end=" ")
print("")

Submission status: Runtime Error

Solution code:
import sys


def dfs1(v, p):
    ret = 1
    links[v].discard(p)
    m = min(v, p)
    for c in links[v]:
        res = dfs1(c, v)
        if c < m:
            ret += res
    subtree_costs[v] = ret
    return ret


def dfs2(v, p, pc):
    sc = pc + subtree_costs[v]
    costs[v] = sc
    m = min(v, p)
    for c in links[v]:
        if c < m:
            dfs2(c, v, sc - subtree_costs[c])
        else:
            dfs2(c, v, sc)


n = int(input())
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
link = [sorted(l) for l in links]
subtree_costs = [0] * n
dfs1(0, -1)
subtree_costs[0] = 0
costs = [0] * n
dfs2(0, -1, 0)
print(*costs[1:])

Submission status: Runtime Error

Solution code:
N = int(input())

X = [[] for i in range(N)]
P = [-1] * 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)


def set_parent(i):
    # print(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            # print(a)
            X[a].remove(i)
            set_parent(a)
    
set_parent(0)

B = [-1] * N
def set_block(i):
    for a in X[i]:
        B[a] = max(i, B[i])
        set_block(a)

B_id = [-1] * N
B_id_cnt = [0] * N
def BID(i):
    for a in X[i]:
        if a > B[a]:
            B_id[a] = a
        else:
            B_id[a] = B_id[i]
            
        # print(a, B_id)
        B_id_cnt[B_id[a]] += 1
        BID(a)
        
Ans = [0] * N
def flow(i):
    for a in X[i]:
        if B_id[a] == B_id[i]:
            Ans[a] = Ans[i]
        else:
            Ans[a] = Ans[i] + B_id_cnt[a]
        flow(a)

set_block(0)
BID(0)
flow(0)

# print("X=", X) # 子リスト
# print("P=", P) # 親
# print("B=", B) # Block
# print(B_id) # BlockのID
# print(B_id_cnt) # BlockのID
# print(Ans)
print(" ".join(map(str, Ans[1:])))

Submission status: Runtime Error

Solution code:
N = int(input())

X = [[] for i in range(N)]
P = [-1] * 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)


def set_parent(i):
    # print(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            # print(a)
            X[a].remove(i)
            set_parent(a)
    
set_parent(0)

B = [-1] * N
def set_block(i):
    for a in X[i]:
        B[a] = max(i, B[i])
        set_block(a)

B_id = [-1] * N
B_id_cnt = [0] * N
def BID(i):
    for a in X[i]:
        if a > B[i]:
            B_id[a] = a
        else:
            B_id[a] = B_id[i]
            
        # print(a, B_id)
        B_id_cnt[B_id[a]] += 1
        BID(a)
        
Ans = [1] * N
def flow(i):
    for a in X[i]:
        if B_id[a] == B_id[i]:
            Ans[a] = Ans[i]
        else:
            Ans[a] = Ans[i] + B_id_cnt[a]
        flow(a)

set_block(0)
BID(0)

# print("X=", X) # 子リスト
# print("P=", P) # 親
# print("B=", B) # Block
# print(B_id) # BlockのID
# print(B_id_cnt) # BlockのID
# print(Ans)
print(" ".join(map(str, Ans[1:])))

Submission status: Runtime Error

Solution code:
N = int(input())

X = [[] for i in range(N)]
P = [-1] * 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)


def set_parent(i):
    # print(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            # print(a)
            X[a].remove(i)
            set_parent(a)
    
set_parent(0)

B = [-1] * N
def set_block(i):
    for a in X[i]:
        B[a] = max(i, B[i])
        set_block(a)

B_id = [-1] * N
B_id_cnt = [0] * N
def BID(i):
    for a in X[i]:
        if a > B[i]:
            B_id[a] = a
        else:
            B_id[a] = B_id[i]
            
        # print(a, B_id)
        B_id_cnt[B_id[a]] += 1
        BID(a)
        
Ans = [1] * N
def flow(i):
    for a in X[i]:
        if B_id[a] == B_id[i]:
            Ans[a] = Ans[i]
        else:
            Ans[a] = Ans[i] + B_id_cnt[a]
        flow(a)

set_block(0)


# print("X=", X) # 子リスト
# print("P=", P) # 親
# print("B=", B) # Block
# print(B_id) # BlockのID
# print(B_id_cnt) # BlockのID
# print(Ans)
print(" ".join(map(str, Ans[1:])))

Submission status: Runtime Error

Solution code:
N = int(input())

X = [[] for i in range(N)]
P = [-1] * 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)


def set_parent(i):
    # print(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            # print(a)
            X[a].remove(i)
            set_parent(a)
    
set_parent(0)

B = [-1] * N
def set_block(i):
    for a in X[i]:
        B[a] = max(i, B[i])
        set_block(a)

B_id = [-1] * N
B_id_cnt = [0] * N
def BID(i):
    for a in X[i]:
        if a > B[i]:
            B_id[a] = a
        else:
            B_id[a] = B_id[i]
            
        # print(a, B_id)
        B_id_cnt[B_id[a]] += 1
        BID(a)
        
Ans = [0] * N
def flow(i):
    for a in X[i]:
        if B_id[a] == B_id[i]:
            Ans[a] = Ans[i]
        else:
            Ans[a] = Ans[i] + B_id_cnt[a]
        flow(a)

set_block(0)
BID(0)
flow(0)

# print("X=", X) # 子リスト
# print("P=", P) # 親
# print("B=", B) # Block
# print(B_id) # BlockのID
# print(B_id_cnt) # BlockのID
# print(Ans)
print(" ".join(map(str, Ans[1:])))