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: Wrong Answer

Solution code:
import queue
N, u, v = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N - 1)] 

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

for i in range(N - 1): 
        children[AB[i][0]].append(AB[i][1])
        children[AB[i][1]].append(AB[i][0])

def aoki(u, v): 
        atot = [[-1, 0] for i in range(N + 1)] 
        atot[v][0] = 0 
        q = queue.Queue()    
        for i in children[v]:
                q.put([i, v]) 
        while not q.empty():
                nt = q.get()
                if nt[0] == u:
                        atot[nt[0]] = [atot[nt[1]][0] + 1, nt[1]]
                        break
                else:
                        for i in children[nt[0]]:
                                if atot[i][0] == -1: 
                                        q.put([i, nt[0]])
                        atot[nt[0]] = [atot[nt[1]][0] + 1, nt[1]]
        bk = u 
        rout = [bk]
        while atot[bk][0] > 0:
                rout.append(atot[bk][1])
                bk = atot[bk][1]

        return rout

def takahashi(u, v): 
        froma = [[-1, 0] for i in range(N + 1)] 
        froma[u][0] = 0 
        q = queue.Queue()    
        for i in children[u]:
                q.put([i, u]) 
        mx = -1
        while not q.empty():
                nt = q.get()
                for i in children[nt[0]]:
                        if froma[i][0] == -1 and nt[0] != v:
                                q.put([i, nt[0]])
                froma[nt[0]] = [froma[nt[1]][0] + 1, nt[1]]
                if froma[nt[0]][0] > mx:
                        g = nt[0]
                        mx = froma[nt[0]][0]
        rout = aoki(g, u)
        if rout[-2] == v:
                aw = v
                for i in children[u]:
                        if i != v:
                                aw = i
                                return aw
                if aw == v:
                        return v
        else:
                return rout[-2]

cnt = 0
while True:
        u = takahashi(u, v)
        if u == v:
                break
        r = aoki(u, v)
        if len(r) == 1:
                v = r[0]
        else:
                v = r[-2]
        if u == v:
                cnt += 1
                break
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, u, v = LI_()
    n += 1
    edg = [[] for i in range(n)]
    for _ in range(n-1):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    dist_u = [-1] * n
    dist_u[u] = 0
    dist_v = [-1] * n
    dist_v[v] = 0
    q = deque([u])
    while q:
        p = q.pop()
        dp = dist_u[p]
        for e in edg[p]:
            if dist_u[e] < 0:
                dist_u[e] = dp + 1
                q.append(e)
    q = deque([v])
    while q:
        p = q.pop()
        dp = dist_v[p]
        for e in edg[p]:
            if dist_v[e] < 0:
                dist_v[e] = dp + 1
                q.append(e)
    ans = 0
    while dist_u[v] - dist_u[u] > 2:
        for e in edg[u]:
            if dist_v[e] < dist_v[u]:
                u = e
                continue
        for e in edg[v]:
            if dist_u[v] > dist_u[e]:
                v = e
                continue
        ans += 1
    f = dist_u[v]-dist_u[u] == 2
    ans -= f
    q = deque([u])
    dist_u = [-1] * n
    for e in edg[v]:
        dist_u[e] = 1
    dist_u[u] = 0
    while q:
        u = q.pop()
        dp = dist_u[u]
        for e in edg[u]:
            if dist_u[e] < 0 and v != e:
                dist_u[e] = dp + 1
                q.append(e)
    if f and max(dist_u) == 1:
        ans += 1
    print(max(dist_u)+ ans)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100010)

n,u,v = [int(i)-1 for i in input().split()]
n+=1
AB = [[int(i)-1 for i in input().split()] for _ in range(n-1)]

nodes = [[] for _ in range(n)]
for ab in AB:
    nodes[ab[1]].append(ab[0])
    nodes[ab[0]].append(ab[1])

route = []
def search(p,before=-1):
    if len(nodes[p])==1 and p!=u:
        return False
    for node in nodes[p]:
        if node == before:
            continue
        if search(node,p) or node==v:
            route.append(p)
            return True
    return False
search(u)
route.reverse()
key = route[(len(route)-1)//2]
if len(route) == 1:
    nodes[key].remove(v)
else:
    nodes[key].remove(route[(len(route)-1)//2+1])

que = [key]
time = -1
while len(que)>0:
    time+=1
    newque = []
    while len(que)>0:
        p = que.pop()
        for q in nodes[p]:
            nodes[q].remove(p)
            newque.append(q)
    que=newque
time = max(0,time)

print( (len(route)-1)//2+time )

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, u, v = LI_()
    n += 1
    edg = [[] for i in range(n)]
    for _ in range(n-1):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    dist_u = [-1] * n
    dist_u[u] = 0
    dist_v = [-1] * n
    dist_v[v] = 0
    q = deque([u])
    while q:
        p = q.pop()
        dp = dist_u[p]
        for e in edg[p]:
            if dist_u[e] < 0:
                dist_u[e] = dp + 1
                q.append(e)
    q = deque([v])
    while q:
        p = q.pop()
        dp = dist_v[p]
        for e in edg[p]:
            if dist_v[e] < 0:
                dist_v[e] = dp + 1
                q.append(e)
    ans = 0
    while dist_u[v] - dist_u[u] > 2:
        for e in edg[u]:
            if dist_v[e] < dist_v[u]:
                u = e
                continue
        for e in edg[v]:
            if dist_u[v] > dist_u[e]:
                v = e
                continue
        ans += 1
    q = deque([u])
    dist_u = [-1] * n

    for e in edg[v]:
        dist_u[e] = 1
    dist_u[u] = 0
    while q:
        u = q.pop()
        dp = dist_u[u]
        for e in edg[u]:
            if dist_u[e] < 0 and v != e:
                dist_u[e] = dp + 1
                q.append(e)
    print(max(dist_u)+ ans)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, u, v = LI_()
    n += 1
    edg = [[] for i in range(n)]
    for _ in range(n-1):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    dist_u = [-1] * n
    dist_u[u] = 0
    dist_v = [-1] * n
    dist_v[v] = 0
    q = deque([u])
    while q:
        p = q.pop()
        dp = dist_u[p]
        for e in edg[p]:
            if dist_u[e] < 0:
                dist_u[e] = dp + 1
                q.append(e)
    q = deque([v])
    while q:
        p = q.pop()
        dp = dist_v[p]
        for e in edg[p]:
            if dist_v[e] < 0:
                dist_v[e] = dp + 1
                q.append(e)
    ans = 0
    while dist_u[v] - dist_u[u] > 2:
        for e in edg[u]:
            if dist_v[e] < dist_v[u]:
                u = e
                continue
        for e in edg[v]:
            if dist_u[v] > dist_u[e]:
                v = e
                continue
        ans += 1
    q = deque([u])
    dist_u = [-1] * n
    dist_u[u] = 0
    for e in edg[v]:
        dist_u[e] = 1
    while q:
        u = q.pop()
        dp = dist_u[u]
        for e in edg[u]:
            if dist_u[e] < 0 and v != e:
                dist_u[e] = dp + 1
                q.append(e)
    print(max(dist_u)+ ans)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

G = [[] for _ in range(N)]
elens = [0] * N

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

def dfs_aoki(cur: int, past: int, d: int):

    if elens[cur] == 1 and G[cur][0] == past:
        pass
#        return [d - 1, 0 if cur == u else -1]

    ret = 0
    takahashi_d = -1

    for nx in G[cur]:
        if nx == past:
            continue

        r = dfs_aoki(nx, cur, d + 1)
#        depth, td = r[0], r[1]
        depth, td = 0, 0
        if td >= 0:
            if td >= 0 and d <= td + 1:
                pass
#                return depth, td
            takahashi_d = td + 1

        ret = max(ret, depth)

#    return [ret, takahashi_d]

#ret = dfs_aoki(v, -1, 0)
#print(ret[0])
print(100)

Submission status: Wrong Answer

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

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

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


TAKAHASHI = [0] * N

def dfs_takahashi(cur: int, past: int, G, d: int):
    TAKAHASHI[cur] = d

    for nx in G[cur]:
        if nx == past:
            continue
        dfs_takahashi(nx, cur, G, d + 1)

def dfs_aoki(cur: int, past: int, G, d: int):

    if len(G[cur]) == 1 and G[cur][0] == past:
        return d - 1, False

    ret = 0
    ret_te = cur == u

    for nx in G[cur]:
        if nx == past:
            continue

        depth, takahashi_exists = dfs_aoki(nx, cur, G, d + 1)
        if takahashi_exists and d <= TAKAHASHI[cur]:
            return depth, True

        ret = max(ret, depth)
        ret_te |= takahashi_exists

    return ret, ret_te

dfs_takahashi(u, -1, G, 0)
d, _ = dfs_aoki(v, -1, G, 0)
print(d)

Submission status: Wrong Answer

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

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

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

def dfs(x, p, d, dep):
    dep[x] = d
    for i in G[x]:
        if i==p:
            pass
        else:
            dfs(i,x,d+1, dep)
    return dep

du = [0]*N
dv = [0]*N
du = dfs(u,-1,0, du)
dv = dfs(v,-1,0, dv)

ans = 0


def dfs2(x, p, d):
    global ans
    for i in G[x]:
        if i==p:
            pass
        elif  du[i]<dv[i]:
            dfs2(i,x, d+1)
        elif du[i]==dv[i]:
            ans = max(ans, d+1)
    ans = max(ans, d)

dfs2(u,-1,0)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
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())
  a-=1;b-=1
  graph[a].append(b)
  graph[b].append(a)
Q=deque([v-1])
Vert=[[0,0] for i in range(n)]
visited=[False]*n
visited[v-1]=True
while Q:
  V=Q.popleft()
  visited[V]=True
  for i in graph[V]:
    if visited[i]:continue
    if i == V:continue
    Vert[i][0]=Vert[V][0]+1
    Q.append(i)
visited=[False]*n
visited[u-1]=True
while Q:
  V=Q.popleft()
  visited[V]=True
  for i in graph[V]:
    if visited[i]:continue
    if i == V:continue
    Vert[i][1]=Vert[V][1]+1
    Q.append(i)
ans=0
for i in Vert:
  if i[0]>i[1]:
    if i[0]>ans:
      ans=i[0]
print(ans-1)

Submission status: Wrong Answer

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

dist = [100005]*(n+1)

q = []
q.append(v)
dist[v] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist[next] == 100005:
            q.append(next)
            dist[next] = dist[now] + 1

dist[0] = 0
print(max(dist)-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,V,U = LI()
V -= 1
U -= 1

edges = [[] for _ in range(n)]

for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

if n == 2:
    print(0)
    quit()

depth = [None]*n
par = [None]*n
depth[U] = 0
par[U] = U
que = deque()
que.append(U)
while que:
    v = que.popleft()
    for u in edges[v]:
        if depth[u] == None:
            depth[u] = depth[v] + 1
            par[u] = v
            que.append(u)

M = max(depth)
L = []
for i in range(n):
    if depth[i] == M:
        L.append(i)
lst = []
tmp = V
while 1:
    if tmp == U:
        break
    tmp = par[tmp]
    lst.append(tmp)

C = inf
T = 0
while L:
    tmp = par[L.pop()]
    cnt = 0
    while 1:
        if tmp in lst:
            break
        tmp = par[tmp]
        cnt += 1
    if C > cnt:
        C = cnt
        T = tmp

if depth[T] > C:
    print(max(depth)-1)
else:
    print(depth[V]-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,V,U = LI()
V -= 1
U -= 1

edges = [[] for _ in range(n)]

for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

if n == 2:
    print(0)
    quit()

depth = [None]*n
par = [None]*n
depth[U] = 0
par[U] = U
que = deque()
que.append(U)
while que:
    v = que.popleft()
    for u in edges[v]:
        if depth[u] == None:
            depth[u] = depth[v] + 1
            par[u] = v
            que.append(u)

M = max(depth)
L = []
for i in range(n):
    if depth[i] == M:
        L.append(i)

C = inf
T = 0
while L:
    tmp = par[L.pop()]
    lst = []
    lst.append(tmp)
    while 1:
        if tmp == U:
            break
        tmp = par[tmp]
        lst.append(tmp)
    tmp = V
    cnt = 0
    while 1:
        if tmp in lst:
            break
        tmp = par[tmp]
        cnt += 1
    if C > cnt:
        C = cnt
        T = tmp

if depth[T] > C:
    print(max(depth)-1)
else:
    print(depth[V]-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,V,U = LI()
V -= 1
U -= 1

edges = [[] for _ in range(n)]

for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

if n == 2:
    print(0)
    quit()

depth = [None]*n
par = [None]*n
depth[U] = 0
par[U] = U
que = deque()
que.append(U)
while que:
    v = que.popleft()
    for u in edges[v]:
        if depth[u] == None:
            depth[u] = depth[v] + 1
            par[u] = v
            que.append(u)

M = max(depth)
L = []
for i in range(n):
    if depth[i] == M:
        L.append(i)

C = inf
while L:
    tmp = par[L.pop()]
    lst = []
    lst.append(tmp)
    while 1:
        if tmp == U:
            break
        tmp = par[tmp]
        lst.append(tmp)
    tmp = V
    cnt = 0
    while 1:
        if tmp in lst:
            break
        tmp = par[tmp]
        cnt += 1
    C = min(C,cnt)

if depth[tmp] > C:
    print(max(depth)-1)
else:
    print(depth[V]-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,V,U = LI()
V -= 1
U -= 1

edges = [[] for _ in range(n)]

for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

if n == 2:
    print(0)
    quit()

depth = [None]*n
par = [None]*n
depth[U] = 0
par[U] = U
que = deque()
que.append(U)
while que:
    v = que.popleft()
    for u in edges[v]:
        if depth[u] == None:
            depth[u] = depth[v] + 1
            par[u] = v
            que.append(u)

tmp = par[depth.index(max(depth))]
lst = []
lst.append(tmp)
while 1:
    if tmp == U:
        break
    tmp = par[tmp]
    lst.append(tmp)
tmp = V
cnt = 0
while 1:
    if tmp in lst:
        break
    tmp = par[tmp]
    cnt += 1

if depth[tmp] > cnt:
    print(max(depth)-1)
else:
    print(depth[V]-1)

Submission status: Wrong Answer

Solution code:
print("reference: maspy")

N, U, V = map(int, input().split())

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

# maspyさんのおかげで、dfsとbfsが一貫して組めている。
def dfs(v): # dfsやbfsはgcdやroot_find、mergeと同様のものと考える。	
    dist = [-1] * (N + 1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        for w in graph[v]:
            if dist[w] != -1:
                continue
            dist[w] = dist[v] + 1
            stack.append(w)
    return dist

DU = dfs(U) # Takahashi
DV = dfs(V) # Aoki
print(DU)
print(DV)
 
answer = []
for i  in range(1, N + 1):
  if DU[i] < DV[i]:
    answer.append(DV[i] - 1)

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
 
N, u, v = map(int, input().split())
 
u -= 1
v -= 1
 
graph = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
 
lst = []
def calcDist(cur, par, dst):
    global lst
    lst[cur] = dst
    for neighbour in graph[cur]:
        if neighbour == par: continue
        calcDist(neighbour, cur, dst + 1)
        
uDist = [None for i in range(N)]
vDist = [None for i in range(N)]
lst = uDist
calcDist(u, -1, 0)
lst = vDist
calcDist(v, -1, 0)
 
best = 0
# uDoes hiding, vdoes searching
for node in range(N):
    if uDist[node] < vDist[node]:
        if vDist[node]%2==uDist[node]%2:
            best = max(best, vDist[node])
        else:
            best = max(best, max(vDist[n] for n in graph[node]))
    if uDist[node] == vDist[node]:
        if any((vDist[n] == uDist[n] and vDist[n] < vDist[node]) for n in graph[node]): continue
        best = max(best, vDist[node])
print(best)

Submission status: Wrong Answer

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

def Dfs(x):
  X = [-1] * (N + 1)
  stack = [x]
  X[x] = 0
  while stack:
    s = stack.pop()
    for g in graph[s]:
      if X[g] == -1:
        X[g] = X[s] + 1
        stack.append(g)
  return X

T = Dfs(u)
A = Dfs(v)
print("T:", T)
print("A:", A)

answer = []
for i in range(1, N + 1):
  if A[i] > T[i]:
    if len(graph[i]) == 0 and A[i] - T[i] == 1:
      answer.append(T[i])
    else:
      answer.append(T[i] + (A[i] - T[i]) // 2)
print(max(answer))

Submission status: Wrong Answer

Solution code:
def dfs(g,root,ds):
    q = [root]
    ds[root] = 0
    while q:
        v = q.pop()
        for c in g[v]:
            if ds[c] == -1:
                ds[c] = ds[v] + 1
                q.append(c)
        



# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
#n = int(input())
n,u,v = [int(i) for i in readline().split()]
u -= 1
v -= 1
 
g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)
 
ds = [-1]*n
dg = [-1]*n

dfs(g,u,ds)
dfs(g,v,dg)

#print(ds,dg)

ans = 0
for i,j in zip(ds,dg):
    if i < j: ans = max((j-i)//2 + i,ans)#; print(i,(j-i)//2)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,u,v=map(int,input().split())
l=[[] for i in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
d1=[-1 for i in range(n+1)]
def dfs(num,now):
  d1[num]=now
  dic=l[num]
  for i in dic:
    if d1[i]!=-1:
      pass
    else:
      dfs(i,now+1)
dfs(u,0)
d2=[-1 for i in range(n+1)]
def dfs1(num,now):
  d2[num]=now
  dic=l[num]
  for i in dic:
    if d2[i]!=-1:
      pass
    else:
      dfs1(i,now+1)
dfs1(v,0)
ans=0
for i in range(1,n+1):
  if d2[i]<d1[i]:
    pass
  else:
    if d2[i]%2!=d1[i]%2:
      ans1=d2[i]-1
    else:
      ans1=d2[i]
    ans=max(ans,ans1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,u,v=map(int,input().split())
l=[[] for i in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
d1=[-1 for i in range(n+1)]
def dfs(num,now):
  d1[num]=now
  dic=l[num]
  for i in dic:
    if d1[i]!=-1:
      pass
    else:
      dfs(i,now+1)
dfs(u,0)
d2=[-1 for i in range(n+1)]
def dfs1(num,now):
  d2[num]=now
  dic=l[num]
  for i in dic:
    if d2[i]!=-1:
      pass
    else:
      dfs1(i,now+1)
dfs1(v,0)
ans=0
for i in range(1,n+1):
  if d2[i]>=d1[i]:
    pass
  else:
    if d2[i]%2!=d1[i]%2:
      ans1=d1[i]
    else:
      ans1=d1[i]
    ans=max(ans,ans1)
print(ans)

Submission status: Wrong Answer

Solution code:
n,ta,ao = map(int,input().split())
ta,ao = ta-1,ao-1
tree_list = [[] for i in range(n)]
ans = 0
for i in range(n-1):
	a,b = map(int,input().split())
	a,b = a-1,b-1
	tree_list[a].append(b)
	tree_list[b].append(a)

def find_tree(tree:list,start:int) -> list:
	depth = [-1]*n
	stack = [tree[start]]
	depth[start] = 0
	dep = 1
	while stack:
		S = stack
		stack = []
		for s in S:
			for ttt in s:
				if depth[ttt] != -1:
					continue
				elif ttt == ao:
					depth[ttt] = 0
					continue
				depth[ttt] = dep
				stack.append(tree[ttt])
		dep += 1
	return depth

taka_tree = find_tree(tree_list,ta)
aoki_tree = find_tree(tree_list,ao)
for t,a in zip(taka_tree,aoki_tree):
	if t < a:
		ans = max(ans,a-1)

print(ans)

Submission status: Wrong Answer

Solution code:
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)

def bfs(s):
  dist = [-1]*N
  que = [s-1]
  while que:
    v = que.pop()
    d = dist[v]
    for w in edge[v]:
      if dist[w]>-1: continue
      dist[w] = d+1
      que.append(w)
  return dist

ud,vd,ans = bfs(u),bfs(v),0
for ud_i,vd_i in zip(ud,vd): ans = max(ans, vd_i-1) if ud_i<vd_i else ans
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
INF = 10**9

n, u, v = [int(item) for item in input().split()]
u -= 1; v -= 1
edge = [[] for _ in range(n)]

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

depth = [0] * n
def calc_depth(p, v, d):
    depth[v] = d
    for nv in edge[v]:
        if nv == p:
            continue
        calc_depth(v, nv, d+1)

calc_depth(-1, v, 0)
frm = depth[v]
too = depth[u]
up = (too - frm - 1) // 2
max_depth = too 

def dfs(p, v, lim):
    global max_depth
    max_depth = max(max_depth, depth[v])
    for nv in edge[v]:
        if nv == p:
            continue
        if depth[v] < lim:
            continue
        dfs(v, nv, lim)

dfs(-1, u, too - up)

if too == 1 and max_depth == 1:
    print(0)
    exit()
if too == 2 and max_depth == 2:
    print(-1)
    exit()

ans = 0
ans = max_depth - frm - 1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
INF = 10**9

n, u, v = [int(item) for item in input().split()]
u -= 1; v -= 1
edge = [[] for _ in range(n)]

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

depth = [0] * n
def calc_depth(p, v, d):
    depth[v] = d
    for nv in edge[v]:
        if nv == p:
            continue
        calc_depth(v, nv, d+1)

calc_depth(-1, v, 0)
frm = depth[v]
too = depth[u]
up = (too - frm - 1) // 2
max_depth = too 

def dfs(p, v, lim):
    global max_depth
    max_depth = max(max_depth, depth[v])
    for nv in edge[v]:
        if nv == p:
            continue
        if depth[v] < lim:
            continue
        dfs(v, nv, lim)

dfs(-1, u, too - up)

if too == 1 and max_depth == 1:
    print(-1)
    exit()
if too == 2 and max_depth == 2:
    print(1)
    exit()

ans = 0
ans = max_depth - frm - 1
print(ans)

Submission status: Wrong Answer

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

"""
高橋くんの戦略
最も遠くに行けるなら言って往復
そのためには、遠くに行くときのポイントに青木より早く到達しなければいけない
青木くん -> 最も遠くに向かって進んでいく
"""

from collections import deque
# 木構造を作る
G = [[] for i in range(N)]
for i in range(N-1):
    # グラフに頂点を追加(距離があるときは,u,vの後に入れる)
    u,v = map(int,input().split())
    G[u-1].append((v-1))
    G[v-1].append((u-1))

# 木をBFSをする
used = [-1] * N
used[V-1] = 0 # 始めどこから行くか

q = deque([V-1])
while len(q) > 0:
    a = q.popleft()
    Vs = G[a]
    for u in Vs: # 頂点以外の要素がグラフにあるときはここ
        if used[u] == -1:
            q.append(u)
            # なにか処理を書きたいときはここに書く
            used[u] = used[a] + 1


used_t = [-1] * N
used_t[U-1] = 0 # 始めどこから行くか
q = deque([U-1])
while len(q) > 0:
    a = q.popleft()
    Vs = G[a]
    for u in Vs: # 頂点以外の要素がグラフにあるときはここ
        if used_t[u] == -1:
            q.append(u)
            # なにか処理を書きたいときはここに書く
            used_t[u] = used_t[a] + 1
# print(used)
# print(used_t)


diff = []
ind = []
for i,(a,t) in enumerate(zip(used,used_t)):
    diff.append(a-t)
    ind.append((t,i))
# print(diff)
ind.sort(reverse=True)
# print(ind)

start = diff[V-1]
ans = 0
for d_taka,i in ind:
    # print("info",d_taka,i,diff[i])
    if diff[i] < 0:
        continue
    ans = d_taka - 1
    break
print(ans)