Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices. The i-th edge connects Vertex A_i and B_i bidirectionally.

Takahashi is standing at Vertex u, and Aoki is standing at Vertex v.

Now, they will play a game of tag as follows:

1. If Takahashi and Aoki are standing at the same vertex, the game ends. Otherwise, Takahashi moves to a vertex of his choice that is adjacent to his current vertex.

2. If Takahashi and Aoki are standing at the same vertex, the game ends. Otherwise, Aoki moves to a vertex of his choice that is adjacent to his current vertex.

3. Go back to step 1.

Takahashi performs his moves so that the game ends as late as possible, while Aoki performs his moves so that the game ends as early as possible.

Find the number of moves Aoki will perform before the end of the game if both Takahashi and Aoki know each other's position and strategy.

It can be proved that the game is bound to end.

Constraints

2 \leq N \leq 10^5

1 \leq u,v \leq N

u \neq v

1 \leq A_i,B_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N u v
A_1 B_1
:
A_{N-1} B_{N-1}

Output

Print the number of moves Aoki will perform before the end of the game.

Sample Input 1

5 4 1
1 2
2 3
3 4
3 5

Sample Output 1

2

If both players play optimally, the game will progress as follows:

Takahashi moves to Vertex 3.

Aoki moves to Vertex 2.

Takahashi moves to Vertex 5.

Aoki moves to Vertex 3.

Takahashi moves to Vertex 3.

Here, Aoki performs two moves.

Note that, in each move, it is prohibited to stay at the current vertex.

Sample Input 2

5 4 5
1 2
1 3
1 4
1 5

Sample Output 2

1

Sample Input 3

2 1 2
1 2

Sample Output 3

0

Sample Input 4

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

Sample Output 4

5



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


Sample output:
2

Submission status: Accepted

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

N,u,v = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(N-1)]
E = [[] for _ in range(N+1)]
for a,b in edges:
    E[a].append(b)
    E[b].append(a)

depth = [[-1,-1] for _ in range(N+1)] 
depth[v][0] = 0
depth[u][1] = 0
def dfs1(E,v):
    vv = E[v]
    for vvv in vv:
        if depth[vvv][0] == -1:
            depth[vvv][0] = depth[v][0] + 1
            dfs1(E,vvv)

def dfs2(E,v):
    vv = E[v]
    for vvv in vv:
        if depth[vvv][1] == -1:
            depth[vvv][1] = depth[v][1] + 1
            dfs2(E,vvv)
dfs1(E,v)
dfs2(E,u)
depth = sorted(depth, reverse=True)
idx = 0
while True:
    if depth[idx][0] - depth[idx][1] >= 1:
        print(depth[idx][0]-1)
        exit()
    else:
        idx += 1

Submission status: Accepted

Solution code:
from collections import deque
import sys

N, u, v = map(int,input().split())
side = [[]for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    side[a-1].append(b-1)
    side[b-1].append(a-1)
node = [[-1,-1,-1]for i in range(N)]
node[v-1] = [0,v-1,-1]
queue = deque([v-1])
leaf = []
while queue:
    q = queue.popleft()
    hoge = 0
    for i in side[q]:
        if node[i][0] == -1:
            node[i][0] = node[q][0]+1
            node[i][1] = q
            queue.append(i)
            hoge += 1
    if hoge == 0:
        node[q][2] = node[q][0]
        leaf.append(q)

leaf.sort(key = lambda x:node[x][0], reverse=True)
for x in leaf:
    while x != v-1:
        if node[node[x][1]][2] < node[x][2]:
            node[node[x][1]][2] = node[x][2]
            x = node[x][1]
        else:
            x = v-1

u -= 1
turn = 0
while 1:
    turn += 1
    if node[node[u][1]][0] > turn:
        u = node[u][1]
    else:
        next = node[u][1]
        node[node[u][1]][2] = 0
        for i in side[u]:
            if node[i][2] > node[next][2]:
                next = i
        u = next
    if node[u][0] < turn:
        break

print(node[u][0])

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,tk,ao = MI()
    tk-=1
    ao-=1

    AB=LLIN_(N-1)
    edge = [[]for _ in range(N)]
    for a,b in AB:
        edge[a].append(b)
        edge[b].append(a)
    
    dist_from_tk = [-inf]*N
    dist_from_ao = [-inf]*N
    
    dist_from_ao[ao]=0
    q = deque([ao])
    while q:
        fr = q.popleft()
        for to in edge[fr]:
            if dist_from_ao[to]!=-inf:
                continue
            # print(fr,to,dist_from_ao)
            dist_from_ao[to]=dist_from_ao[fr]+1
            q.append(to)
    # print(dist_from_ao)

    dist_from_tk[tk]=0
    q = deque([tk])
    mid = -inf
    add_flag=0
    while q:
        fr = q.popleft()
        for to in edge[fr]:
            if dist_from_tk[to]!=-inf:
                continue
            if dist_from_ao[to]<=dist_from_tk[fr]+1:
                mid = fr
                if(dist_from_ao[to]==dist_from_tk[fr]+1):
                    add_flag=1
                continue
            # print(fr,to,dist_from_tk)
            dist_from_tk[to]=dist_from_tk[fr]+1
            q.append(to)
    # print("#########")
    # print(dist_from_ao)
    # print(dist_from_tk)
    # print(mid)


    dist_from_mid = [-inf]*N
    dist_from_mid[mid]=0
    q = deque([mid])
    while q:
        fr = q.popleft()
        for to in edge[fr]:
            if dist_from_mid[to]!=-inf:
                continue
            if dist_from_tk[to]==-inf:#到達不可
                continue
            # print(fr,to,dist_from_mid)
            dist_from_mid[to]=dist_from_mid[fr]+1
            q.append(to)
    # print(dist_from_mid)
    
    if dist_from_ao[tk]==1 and max(dist_from_tk)==0: ##自滅
        print(0)
    elif max(dist_from_tk)==0: ##動いたらすぐ死ぬ
        print(1)
    else:
        ans = dist_from_tk[mid]+max(dist_from_mid)
        print(ans+add_flag)
    # print(dist_from_tk[mid],max(dist_from_mid))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, u, v = map(int, input().split())
u -= 1
v -= 1

e_list = [[] for _ in range(N)]

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

def calc_depth_table(v):
	queue = [[v, None, 0]]
	depth_table = [0] * N
	depth_table[v] = 0
	
	while queue:
		cur, pre, depth = queue.pop()
		depth += 1
		for n in e_list[cur]:
			if n != pre:
				queue.append([n, cur, depth])
				depth_table[n] = depth
	return depth_table

def calc_depth_table2(depth_from_v, u):
	queue = [[u, None, 0, depth_from_v[u], u]]
	depth_table = [0] * N
	depth_table[u] = (0, depth_from_v[u], u)
	
	while queue:
		cur, pre, depth, min_depth_from_v, min_depth_point = queue.pop()
		depth += 1
		for n in e_list[cur]:
			if n != pre:
				depth2 = depth_from_v[n]
				if min_depth_from_v > depth2:
					new_min_depth = depth2
					new_min_depth_point = n
				else:
					new_min_depth = min_depth_from_v
					new_min_depth_point = min_depth_point
				queue.append([n, cur, depth, new_min_depth, new_min_depth_point])
				depth_table[n] = (depth, new_min_depth, new_min_depth_point)
	return depth_table

depth_from_v = calc_depth_table(v)
depth_from_u = calc_depth_table2(depth_from_v, u)

#print(depth_from_v)
#print(depth_from_u)

max_count = 0
for i in range(N):
	a_dist = depth_from_v[i]
	t_dist, a_hit_dist, hit_pos = depth_from_u[i]
	t_hit_dist = depth_from_u[hit_pos][0]
	
#	print(t_hit_dist, a_hit_dist)
	if t_hit_dist < a_hit_dist:
#		print(t_hit_dist, a_hit_dist)
#		if (a_hit_dist - t_hit_dist) % 2 == 1:
		if max_count < a_dist - 1:
			max_count = a_dist - 1
#			else:
#				

print(max_count)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,u,v = inm()
u -= 1
v -= 1
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    dst[a-1].append(b-1)
    dst[b-1].append(a-1)
# dist from v
dist = [-1]*n
q = [(v,0)]
while len(q)>0:
    i,d = q.pop()
    dist[i] = d
    for j in dst[i]:
        if dist[j] == -1:
            q.append((j,d+1))
# from u to mid(r)
r = dist[u]//2+1
t = dist[u]
w = u
while t>r:
    for z in dst[w]:
        if dist[z] == t-1:
            w = z
            t -= 1
            break
# longest path from w
searched = [-1]*n
searched[w] = True
mx = t
q = [w]
while len(q)>0:
    x = q.pop()
    for y in dst[x]:
        if dist[y]>dist[x]:
            q.append(y)
            mx = max(mx,dist[y])
print(mx-1)

Submission status: Accepted

Solution code:
import sys


def inpl():
    return list(map(int, input().split()))


def set_depth(i):
    for e in edge[i]:
        if depth[e] != -1:
            continue
        depth[e] = depth[i] + 1
        parent[e] = i
        set_depth(e)
    return


def get_root_v(can_depth, u):
    if depth[u] == can_depth:
        return u
    else:
        return get_root_v(can_depth, parent[u])


def find_max_depth(v):
    if len(edge[v]) == 1 and parent[v] == edge[0]:
        return depth[v]

    tmp = depth[v]
    for e in edge[v]:
        if parent[v] == e:
            continue
        else:
            tmp = max(tmp, find_max_depth(e))
    return tmp


sys.setrecursionlimit(2 * 10**6)

N, u, v = inpl()
AB = [inpl() for _ in range(N - 1)]
edge = [[] for i in range(N + 1)]
for a, b in AB:
    edge[a].append(b)
    edge[b].append(a)

depth = [-1 for i in range(N + 1)]
depth[v] = 0

parent = [-1 for i in range(N + 1)]

set_depth(v)

can_depth = depth[u] - (depth[u] - 1) // 2
root_v = get_root_v(can_depth, u)

print(find_max_depth(root_v) - 1)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfsv(u,pu=-1,d=0):
        dist[u]=d
        for cu in to[u]:
            if cu==pu:continue
            dfsv(cu,u,d+1)

    def dfsu(u,pu=-1,d=0):
        res=dist[u]
        for cu in to[u]:
            if cu==pu:continue
            if dist[cu]>d+1:
                ret=dfsu(cu,u,d+1)
                if ret>res:res=ret
        return res

    to=defaultdict(list)
    n,u,v=MI()
    u,v=u-1,v-1
    for _ in range(n-1):
        a,b=MI1()
        to[a].append(b)
        to[b].append(a)
    dist=[0]*n
    dfsv(v)
    #print(dist)
    print(dfsu(u)-1)




main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
n,u,v=map(int,input().split())
u=u-1
v=v-1
root=[[] for i in range(n)]

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

dp=[[-1]*n for i in range(2)]
dp[0][u]=0
dp[1][v]=0
def dfs(node,depth,par,flag):
    for vertex in root[node]:
        if vertex == par or dp[flag][vertex]!=-1:
            continue
        dp[flag][vertex]=depth+1
        dfs(vertex,depth+1,node,flag)
    return
dfs(u,0,u,0)
dfs(v,0,v,1)
buf=-1
buf1=0
#print(dp1,dp2,root)
for i in range(n):
    if dp[0][i]<dp[1][i] and dp[1][i]>buf:
        buf=dp[1][i]
        buf1=dp[0][i]
print(buf-1)

Submission status: Accepted

Solution code:
N,u,V = map(int,input().split())

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


# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*N
que = deque([u-1])
dist[u-1] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

from collections import deque
dist2 = [-1]*N
que = deque([V-1])
dist2[V-1] = 0
while que:
    v = que.popleft()
    d = dist2[v]
    for w in G[v]:
        if dist2[w] > -1:
            continue
        dist2[w] = d + 1
        que.append(w)

ans = 0
import math
for d, d2 in zip(dist, dist2):
    if d2 > d:
        ans = max(d2-1, ans)
print(ans)

Submission status: Accepted

Solution code:
words = lambda t : list(map(t, input().split()))

n,u,v = words(int)
u -= 1
v -= 1

edges = [[] for i in range(n)]
for i in range(n-1):
    f,t = words(int)
    edges[f-1].append(t-1)
    edges[t-1].append(f-1)

from queue import Queue
def bfs1(edges,stt):
    dist = [-1] * n
    q = Queue()
    q.put(stt)
    dist[stt] = 0
    #print(q)
    while not q.empty():
        v = q.get()
        #print(v)
        for c in edges[v]:
            #print("es", c)
            if dist[c] == -1:
                dist[c] = dist[v]+1
                q.put(c)
    return dist

dist_v = bfs1(edges, v)
dist_u = bfs1(edges, u)
#print(u,v)
#print(edges)
#print(dist_v)
#print(dist_u)

ans = 0
for i in range(n):
    if dist_v[i] > dist_u[i]:
        ans = max(ans,dist_v[i])

print(max(ans-1,0))

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N, u, v = map(int, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    par = [int(i) for i in range(N)]
    son = [[] for _ in range(N)]
    q = deque()
    for s in edge[v-1]:
        q.append((s, v-1))
        son[v-1].append(s)
    while q:
        now, pre = q.popleft()
        par[now] = pre
        for s in edge[now]:
            if s != pre:
                son[now].append(s)
                q.append((s, now))

    distAT = 0
    Tnow = u-1
    while Tnow != v-1:
        distAT += 1
        Tnow = par[Tnow]
    
    ans = (distAT - 1) // 2
    turn = u - 1
    for _ in range(ans): turn = par[turn]
    dist = [-1] * N
    q.append((turn, 0))
    maxback = 0
    while q:
        now, d = q.popleft()
        maxback = max(maxback, d)
        for s in son[now]: q.append((s, d+1))

    if distAT % 2 == 0:
        ans += maxback + 1
    else: ans += maxback
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import collections
n, u, v = map(int, input().split())
graph = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b - 1].append(a - 1)


dist = [[float('inf')] * n for i in range(2)]
visited = [[False] * n for i in range(2)]
dq = [collections.deque() for i in range(2)]

dq[0].append((0, u-1))
dq[1].append((0, v - 1))

for i in range(2):
    while dq[i]:
        d, v = dq[i].popleft()
        if visited[i][v]:
            continue
        visited[i][v] = True
        dist[i][v] = d
        for nv in graph[v]:
            if visited[i][nv]:
                continue
            dq[i].append((d + 1, nv))

dq[0].append((0, u-1))
visited = [[False] * n for i in range(2)]
i = 0
while dq[i]:
    d, v = dq[i].popleft()
    if visited[i][v]:
        continue
    visited[i][v] = True
    if dist[0][v] >= dist[1][v]:
        continue
    for nv in graph[v]:
        if visited[i][nv]:
            continue
        dq[i].append((d + 1, nv))

max_turn = 0
for i in range(n):
    if not visited[0][i]:
        continue
    max_turn = max(max_turn, dist[1][i]-1)
print(max_turn)

Submission status: Accepted

Solution code:
def djkstra(a,in_connect_list,v):
    out_shortest_list = [10**15 for i in range(v)]
    out_shortest_list[a] = 0
    searching_list = [a]
    
    while searching_list != []:
        new_search_list = []
        for i in searching_list:
            for c in in_connect_list[i]: 
                if out_shortest_list[c] == 10**15:
                    out_shortest_list[c] = 1 + out_shortest_list[i]
                    new_search_list.append(c)
        searching_list = new_search_list
    return out_shortest_list

n, u, v = [ int(v) for v in input().split() ]
u -= 1
v -= 1
connnect = [ [] for i in range(n) ]
for i in range(n-1):
    a, b = [ int(v) for v in input().split() ]
    a -= 1
    b -= 1
    connnect[a].append(b)
    connnect[b].append(a)

takahashi_time = djkstra(u, connnect, n)
aoki_time = djkstra(v, connnect, n)

ans_time = [ aoki_time[i]  for i in range(n) if aoki_time[i] >= takahashi_time[i] ]

print(max(0, max(ans_time)-1))

Submission status: Accepted

Solution code:
n, u, v, *L = map(int, open(0).read().split())
dist_f_v = [-1] * n
con = [[] for _ in range(n)]
for s, t in zip(*[iter(L)] * 2):
	con[s - 1].append(t - 1)
	con[t - 1].append(s - 1)
dist_f_v[v - 1] = 0
q = [v - 1]
while q:
	cur = q.pop()
	for nxt in con[cur]:
		if dist_f_v[nxt] < 0:
			dist_f_v[nxt] = dist_f_v[cur] + 1
			q.append(nxt)
dist_f_u = [-1] * n
dist_f_u[u - 1] = 0
q = [u - 1]
m = 0
while q:
	cur = q.pop()
	m = max(m, dist_f_v[cur])
	for nxt in con[cur]:
		if dist_f_u[nxt] > -1:
			continue
		if dist_f_u[cur] + 1 < dist_f_v[nxt]:
			dist_f_u[nxt] = dist_f_u[cur] + 1
			q.append(nxt)
		elif dist_f_u[cur] + 1 == dist_f_v[nxt]:
			dist_f_u[nxt] = dist_f_u[cur] + 1
print(m - 1)

Submission status: Accepted

Solution code:
def depth(u, E):
    ud = [None] * len(E)
    cur = E[u].copy()
    ud[u] = 0
    d = 1
    while cur:
        nxt = []
        for c in cur:
            ud[c] = d
            for i in E[c]:
                if ud[i] is None:
                    nxt.append(i)
        cur = nxt
        d += 1
    return ud

def main():
    N, u, v = list(map(int, input().split()))
    u, v = u - 1, v - 1
    E = [list() for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        E[a - 1].append(b - 1)
        E[b - 1].append(a - 1)

    ud = depth(u, E)
    vd = depth(v, E)
    m = 0
    for i in range(N):
        udi = ud[i]
        vdi = vd[i]
        if udi >= vdi:
            continue
        steps = udi + (vdi - udi) - 1
        m = max(steps, m)
    print(m)



main()

Submission status: Accepted

Solution code:
N,u,v = list(map(int,input().split()))
u,w = u-1,v-1
w,u = u,w
e_list = [[] for i in range(N)]
for i in range(N-1):
        a,b = list(map(int,input().split()))
        a,b = a-1,b-1
        e_list[a].append(b)
        e_list[b].append(a)

vi = u #時と場合によってここを変える
from collections import deque
Q = deque([vi])
checked_list = [False for i in range(N)]
checked_list[vi]=True
min_path_list = [10**27 for i in range(N)] #問題によりここを変える
min_path_list[vi] = 0
prev_list = [-1 for i in range(N)]
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            prev_list[v1] = v
            Q.appendleft(v1)
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) #問題によりここを変える

dis=min_path_list[w]//2
w_min = min_path_list[w]
current = w
for i in range(dis):
        current = prev_list[current]
dist = min_path_list[current]
vi = current #時と場合によってここを変える
Q = deque([vi])
checked_list = [False for i in range(N)]
checked_list[vi]=True
checked_list[prev_list[vi]]=True
min_path_list = [10**27 for i in range(N)] #問題によりここを変える
min_path_list[vi] = 0
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.appendleft(v1)
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) #問題によりここを変える
depth = 0
for i in range(N):
        if min_path_list[i]<10**27:
                depth = max(min_path_list[i],depth)

depth = dist+depth
print(depth-1)

Submission status: Accepted

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

n,v,u = map(int, input().split()); u -= 1; v -= 1
g = [list() for _ in range(n)]
for _ in range(n-1):
  a,b = map(int, input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
dep = [0]*n; mdep = [0]*n; par = [-1]*n

if u == v: print(0); exit(0)

def dfs(v,p):
  for x in g[v]:
    if x == p:
      continue
    par[x] = v
    dep[x] = dep[v] + 1
    dfs(x,v)
    if mdep[v] < mdep[x] + 1:
      mdep[v] = mdep[x] + 1
  return
      
dfs(u,-1)
t = (dep[v]-1)//2
curv = v
for _ in range(t):
  curv = par[curv]
curu = par[curv]
if not dep[v]%2:
  curu = par[curu]
print(t + mdep[curv] + 1 - dep[v]%2)

Submission status: Accepted

Solution code:
N,u,v = map(int,input().split())
u -=1
v -=1
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]

E = [[] for _ in [0]*N]
for a,b in AB:
    E[a-1].append(b-1)
    E[b-1].append(a-1)

def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        qq = []
        for i in q:
            di = d[i]
            for j in E[i]:
                if d[j]!=-1:continue
                d[j] = di+1
                q.append(j)
        q = qq
    return d

d = dist_bfs(N,E,v)

dt = d[u] - (d[u]-1)//2

w = u
dw = d[w]
while dw != dt:
    for j in E[w]:
        if d[j] == (dw-1):
            w = j
            break
    dw = d[w]
t = w

ans = d[u]-dt

tmp = 0
q = [t]
while q:
    i = q.pop()
    di = d[i]
    tmp = max(tmp,di-dt)
    for j in E[i]:
        if d[j] >di:
            q.append(j)

ans += tmp
ans += 1-d[u]%2

print(ans)

Submission status: Accepted

Solution code:
n,u,v = map(int,input().split())
inf = 10 ** 6
u -= 1
v -= 1
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
seen = [0 for _ in range(n)]
rank = [0 for _ in range(n)]
seen[v] = 1
now = [v]
pst = [[] for _ in range(n)]
pre = [inf for _ in range(n)]
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        rank[y] = rank[x] + 1
        pst[x].append(y)
        pre[y] = x
        now.append(y)
#print(rank)
r = rank[u]
if r % 2 == 0:
  m = r//2 + 1
  M = u
  for _ in range(r-m):
    M = pre[M]
  now = [M]
  while now != []:
    last = now
    now = []
    for x in last:
      for y in pst[x]:
        now.append(y)
  ans = rank[last[0]] - m + r - m + 1
  #print(r,m,M,rank[last[0]],last[0])
  #print(0,ans)
else:
  m = r//2 + 1
  M = u
  for _ in range(r-m):
    M = pre[M]
  now = [M]
  while now != []:
    last = now
    now = []
    for x in last:
      for y in pst[x]:
        now.append(y)
  ans = rank[last[0]] - m + r - m
  #print(r,m,M,rank[last[0]],last[0])
  #print(1,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

u -= 1
v -= 1

def bfs1():
    q = [v]
    d = 0
    D = [-1]*N
    D[v] = 0
    while q:
        qq = []
        d += 1
        for p in q:
            for np in graph[p]:
                if D[np] == -1:
                    D[np] = d
                    qq.append(np)
        q = qq
    return D

D = bfs1()
dis = D[u]
canuse = [True]*N
for i in range(N):
    if D[i] <= dis//2:
        canuse[i] = False

def bfs2():
    q = [u]
    d = 0
    D = [-1]*N
    D[u] = 0
    while q:
        qq = []
        d += 1
        for p in q:
            for np in graph[p]:
                if D[np] == -1 and canuse[np]:
                    D[np] = d
                    qq.append(np)
        q = qq
    return D


D2 = bfs2()
ans = 0
for i in range(N):
    if len(graph[i]) == 1 and D2[i] != -1:
        ans = max(D[i]-1, ans)
print(ans)

Submission status: Accepted

Solution code:
N,U,V = map(int,input().split())
U,V = U-1, V-1

adj = [list() for _ in range(N)]

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



dist_u = [None]*N
dist_u[U] = 0
stack = [U]

while stack:
    x = stack.pop()
    d = dist_u[x]+1
    for y in adj[x]:
        if dist_u[y] is None:
            dist_u[y] = d
            stack.append(y)


dist_v = [None]*N
dist_v[V] = 0
stack = [V]

while stack:
    x = stack.pop()
    d = dist_v[x]+1
    for y in adj[x]:
        if dist_v[y] is None:
            dist_v[y] = d
            stack.append(y)

n = max(b for a,b in zip(dist_u, dist_v) if a < b)
m = min((b for a,b in zip(dist_u, dist_v) if a <= b), default=n)

print(max(n,m)-1)

Submission status: Accepted

Solution code:
from collections import deque

N,u,v = map(int,input().split())
edge = [list(map(int,input().split())) for _ in range(N-1)]

graph = [[] for _ in range(N)]

for e in edge:
    graph[e[0]-1].append(e[1]-1)
    graph[e[1]-1].append(e[0]-1)

level = [-1 for _ in range(N)]
level[v-1] = 0

queue = deque([v-1])

while queue:
    node = queue.popleft()
    for adj in graph[node]:
        if level[adj]==-1:
            level[adj] = level[node] + 1
            queue.append(adj)

t = level[u-1]

stack = [u-1]
maxlevel = t
visited = [0 for _ in range(N)]
visited[u-1] = 0
a = 0

while stack:
    node = stack.pop()
    for adj in graph[node]:
        if not visited[adj] and t-level[adj]<=(t-1)//2:
            stack.append(adj)
            maxlevel = max(maxlevel,level[adj])
            visited[adj] = 1

d = maxlevel-t

print(d+t-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, u, v = list(map(int, input().split()))
E = [[] for _ in range(N)]
for _ in range(N-1):
    A, B = list(map(int, input().split()))
    E[A-1].append(B-1)
    E[B-1].append(A-1)

#print(E)

parent = [None]*N
parent[v-1] = -1
depth = [None]*N
depth[v-1] = 0

queue = [v-1]
d=1
while queue:
    queue_new = []
    for q in queue:
        for e in E[q]:
            if parent[e] is not None: continue
            parent[e] = q
            queue_new.append(e)
            depth[e] = d

    queue = queue_new
    d+=1

#print(parent)
#print(depth)

w = u-1
x = (depth[u-1]-1)//2
for _ in range(x):
    w = parent[w]
    #print('rewind')

#print(w)

depth_from_w = 0
queue = [w]
while queue:
    queue_new = []
    for q in queue:
        for e in E[q]:
            if e==parent[q]: continue
            queue_new.append(e)

    queue = queue_new
    depth_from_w+=1

#print(depth_from_w-1)
print(depth[w] + depth_from_w-2)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,u,v=map(int,input().split())
Edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  Edge[a-1].append(b-1)
  Edge[b-1].append(a-1)


from collections import deque

def BFS(s):
  dist=[-1]*n
  que=deque([s-1])
  dist[s-1]=0
  while que:
    v=que.popleft()
    d=dist[v]
    for w in Edge[v]:
      if dist[w]>-1:
        continue
      dist[w]=d+1
      que.append(w)
  return dist

U_d,V_d=BFS(u),BFS(v)
ans=0
for i in range(n):
  if U_d[i]<V_d[i]:
    ans=max(ans,V_d[i]-1)
print(ans)

Submission status: Accepted

Solution code:
n, u, v = (int(i) for i in input().split())
ablist=[]
onilist=[-1]*n
whelist=[]
sudelist=[0]*n
for i in range(n):
    whelist.append([])

for i in range(n-1):
    a, b = (int(i) for i in input().split())
    ablist.append([a, b])
    whelist[a-1].append(b-1)
    whelist[b-1].append(a-1)

#print(ablist)

onilist[v-1]=0

mark=1
now=[v-1]
turn=1
while mark<n:
    nextis=[]
    for nw in now:
        nextis+=whelist[nw]
    now=[]
    for nx in nextis:
        if onilist[nx]==-1:
            onilist[nx]=turn
            now.append(nx)
            mark+=1
    turn+=1

#print(onilist)

swit=0
nowmax=onilist[u-1]
limit=nowmax//2

now=[u-1]
sudelist[u-1]=1
#print(sudelist, nowmax, limit)
while swit==0:
    nextis=[]
    for nw in now:
        nextis+=whelist[nw]
    now=[]
    #print(nextis)
    for nx in nextis:
        if sudelist[nx]==0 and onilist[nx]>limit:
            now.append(nx)
            sudelist[nx]=1
            if onilist[nx]>nowmax:
                nowmax=onilist[nx]
    #print(now)
    if now==[]:
        swit=1

#print(sudelist)
print(nowmax-1)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
import queue

INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, u, v = getlist()
	u -= 1; v -= 1
	G = Graph()
	for i in range(N - 1):
		A, B = getlist()
		A -= 1; B -= 1
		G.add_edge(A, B)
		G.add_edge(B, A)
	BF_taka = BFS(G, u, N)
	BF_ao = BFS(G, v, N)
	taka_dist = BF_taka.dist
	ao_dist = BF_ao.dist
	dis = 0

	for i in range(N):
		val = taka_dist[i]
		xval = ao_dist[i]
		if val < xval:
			dis = max(dis, xval)
	
	print(dis - 1)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,T,A = map(int, input().split(' '))
ab = [list(map(int, input().split(' '))) for i in range(n-1)]
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
dist = [0 for i in range(n+1)]
root = A
order = []
stack = [root]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        stack.append(y)
for x in order:
    if x == root:
        continue
    dist[x] = 1+dist[parent[x]]
#print(dist)
dist_ini = dist[T]
ans = 0
if dist_ini > 2:
    ans += (dist_ini-1)//2
    for i in range(ans):
        T = parent[T]
    dist_n = (dist_ini-1)%2+1
else:
    dist_n = dist_ini
#print(dist_n,T)
stack = [(T,0)]
dist_final = 0
while stack:
    x,cnt = stack.pop()
    dist_final = max(dist_final,cnt)
    for y in graph[x]:
        if parent[x] == y:
            continue
        stack.append((y,cnt+1))
ans += dist_final
if dist_ini % 2 == 0:
    ans += 1
print(ans)