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:
def main():
    from functools import lru_cache
    import sys
    input=sys.stdin.readline
    sys.setrecursionlimit(1000000)

    n,u,v=map(int,input().split())
    u-=1
    v-=1
    tree=[[] for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        tree[a].append(b)
        tree[b].append(a)
    
    depth=[0]*n
    depth[v]=0
    def dfs(i,before=-1):
        for e in tree[i]:
            if e!=before:
                depth[e]=depth[i]+1
                dfs(e,i)
    dfs(v)

    max_depth=[-1]*n
    max_depth[v]=0
    
    @lru_cache(maxsize=None)
    def dfs2(i,before=-1):
        for e in tree[i]:
            t=-1
            if e!=before:
                t=max(t,dfs2(e,i))
        if t!=-1:
            max_depth[i]=t
            return max_depth[i]
        else:
            max_depth[i]=depth[i]
            return max_depth[i]
            
    dfs2(v)
    
    lim=depth[u]
    i,key=u,u
    ans=0
    while i!=v:
        tmp=max_depth[i]+lim-2*depth[i]
        if 2*depth[i]<lim and ans<tmp:
            ans=tmp
            key=i
        for e in tree[i]:
            if depth[e]<depth[i]:
                i=e
                break
    
    if ans%2==max_depth[key]%2:
        print(max_depth[key])
    else:
        print(max_depth[key]-1) 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from functools import lru_cache
    import sys
    input=sys.stdin.readline
    sys.setrecursionlimit(1000000)

    n,u,v=map(int,input().split())
    u-=1
    v-=1
    tree=[[] for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        tree[a].append(b)
        tree[b].append(a)
    
    depth=[0]*n
    depth[v]=0
    def dfs(i,before=-1):
        for e in tree[i]:
            if e!=before:
                depth[e]=depth[i]+1
                dfs(e,i)
    dfs(v)

    max_depth=[-1]*n
    max_depth[v]=0
    
    @lru_cache(maxsize=None)
    def dfs2(i,before=-1):
        for e in tree[i]:
            t=-1
            if e!=before:
                t=max(t,dfs2(e,i))
        if t!=-1:
            max_depth[i]=t
            return max_depth[i]
        else:
            max_depth[i]=depth[i]
            return max_depth[i]
            
    dfs2(v)
    
    lim=depth[u]
    i,key=u,u
    ans=0
    while i!=v:
        tmp=max_depth[i]+lim-2*depth[i]
        if ans<tmp:
            ans=tmp
            key=i
        for e in tree[i]:
            if depth[e]<depth[i]:
                i=e
                break
    
    if ans%2==max_depth[key]%2:
        print(max_depth[key])
    else:
        print(max_depth[key]-1) 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
def main():
    n, u, v = map(int, input().split())
    graph = [[0]*n for i in range(n)]
    u -= 1
    v -= 1
    for _ in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a][b] = 1
        graph[b][a] = 1
    dist_t = dijkstra(csr_matrix(graph), indices=u)
    dist_a = dijkstra(csr_matrix(graph), indices=v)
    ans = 0
    for i in range(n):
        if dist_t[i] < dist_a[i]:
            buf = int(dist_t[i] + (dist_a[i] - dist_t[i])//2)
            if ans < buf:
                ans = buf
    x = 10**6
    equal_f = False
    for i in range(n):
        if dist_t[i] == dist_a[i]:
            equal_f = True
            buf = dist_t[i]
            if buf < x:
                x = buf
    if equal_f:
        if ans < x:
            ans = x
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
INF = 10 ** 20

def dfs(graph, root, n):
    dista = [INF for i in range(n)]
    visited = [0 for i in range(n)]
    dista[root - 1] = 0
    visited[root - 1] = 1
    d = deque()
    for edge in graph[root - 1]:
        d.append(edge)
    while(d):
        cur, nxt = d.pop()
        if not visited[nxt]:
            dista[nxt] = dista[cur] + 1
            visited[nxt] = 1
            for edge in graph[nxt]:
                d.append(edge)

    return dista

def dfs2(graph, root, n, dista):
    distb = [INF for i in range(n)]
    visited = [0 for i in range(n)]
    visited[root - 1] = 1
    distb[root-1] = 0
    d = deque()
    ans = 0
    # print(dista, distb)
    for edge in graph[root-1]:
        d.append(edge)
    while(d):
        # print(d)
        # print(distb)
        cur, nxt = d.pop()
        if not visited[nxt]:
            if distb[cur] + 1 <= dista[nxt]:
                visited[nxt] = 1
                distb[nxt] = distb[cur] + 1
                for edge in graph[nxt]:
                    d.append(edge)
                if ans < dista[nxt]:
                    ans = dista[nxt]

            # print(ans, cur, nxt, visited)

    return ans

def main():
    n, u, v = getList()
    graph = [[] for i in range(n)]
    dista = [INF for i in range(n)]
    distb = [INF for i in range(n)]
    for i in range(n-1):
        a,b = getList()
        graph[a-1].append((a-1, b-1))
        graph[b - 1].append((b-1, a - 1))
    # print(graph)
    if n == 3:
        print(1)
        return 
    dista = dfs(graph, v, n)
    # print(dista)
    print(max(0, dfs2(graph, u, n, dista) - 1))
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
INF = 10 ** 20

def dfs(graph, root, n):
    dista = [INF for i in range(n)]
    visited = [0 for i in range(n)]
    dista[root - 1] = 0
    visited[root - 1] = 1
    d = deque()
    for edge in graph[root - 1]:
        d.append(edge)
    while(d):
        cur, nxt = d.pop()
        if not visited[nxt]:
            dista[nxt] = dista[cur] + 1
            visited[nxt] = 1
            for edge in graph[nxt]:
                d.append(edge)

    return dista

def dfs2(graph, root, n, dista):
    distb = [INF for i in range(n)]
    visited = [0 for i in range(n)]
    visited[root - 1] = 1
    distb[root-1] = 0
    d = deque()
    ans = 0
    # print(dista, distb)
    for edge in graph[root-1]:
        d.append(edge)
    while(d):
        # print(d)
        # print(distb)
        cur, nxt = d.pop()
        if not visited[nxt]:
            if distb[cur] + 1 <= dista[nxt]:
                visited[nxt] = 1
                distb[nxt] = distb[cur] + 1
                for edge in graph[nxt]:
                    d.append(edge)
                if ans < dista[nxt]:
                    ans = dista[nxt]

            # print(ans, cur, nxt, visited)

    return ans

def main():
    n, u, v = getList()
    graph = [[] for i in range(n)]
    dista = [INF for i in range(n)]
    distb = [INF for i in range(n)]
    for i in range(n-1):
        a,b = getList()
        graph[a-1].append((a-1, b-1))
        graph[b - 1].append((b-1, a - 1))
    # print(graph)

    dista = dfs(graph, v, n)
    # print(dista)
    print(max(0, dfs2(graph, u, n, dista) - 1))
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, r0, g0 = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(n-1)]

connects = [[] for i in range(n+1)]
for e in edges:
    connects[e[0]].append(e[1])
    connects[e[1]].append(e[0])    

import numpy as np
rL, gL = np.array([-1]*(n+1)), np.array([-1]*(n+1))
rL[r0], gL[g0] = 0, 0

from collections import deque
rQ, gQ = deque([r0]), deque([g0])

for L, Q in [(rL, rQ), (gL, gQ)]:
    while Q:
        node = Q.popleft()
        for ni in connects[node]:
            if L[ni] == -1:
                L[ni] = L[node] + 1
                print((node, L[node]), (ni, L[ni]), L)
                Q.append(ni)
    
print(max(gL[i] for i in range(1, n+1) if rL[i] < gL[i]) - 1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

def make_adlist(n):
  adlist = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(lambda x:int(x)-1, input().split())
    adlist[a] += [b] 
    adlist[b] += [a]
  return adlist

def dfs(adlist, s, dist, d):
  for nxt in adlist[s]:
    if dist[nxt] == 0:
      dist[nxt] = d
      dfs(adlist, nxt, dist, d+1)

def main():
  n, u, v = map(int, input().split())
  u -= 1
  v -= 1
  adlist = make_adlist(n)
  t_dist = [0]*n
  t_dist[u] = -1
  dfs(adlist, u, t_dist, 1)
  a_dist = [0]*n
  a_dist[v] = -1
  dfs(adlist, v, a_dist, 1)

  ans = 0 
  for i in range(n):
    if t_dist[i] > a_dist[i]:
      pass
    elif t_dist[i] == a_dist[i]:
      if ans == 0:
        ans = t_dist[i]
      else:
        ans = min(ans, t_dist[i]) 
    else:
      ans = max(ans, t_dist[i])
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
from collections import deque, Counter, defaultdict
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
MOD = 10**9 + 7
INF = 10**20



def dfs(S, F, depth, v, d, graph):
    F[v] = len(S)
    depth[v] = d
    S.append(v)
    for w in graph[v]:
        dfs(S, F, depth, w, d+1, graph)
        S.append(v)


def main():
    n,a,b = getList()
    graph = [[] for i in range(n)]
    for _ in range(n-1):
        v1, v2 = getList()
        graph[v1 - 1].append(v2 - 1)
        graph[v1 - 1].append(v2 - 1)

    S = []
    F = [0] * n
    depth = [0] * n
    dfs(S, F, depth, 0, 0, graph)

    print(S)
    # ret = eulertour(graph)
    # print(ret)

    # revidx = [-1 for i in range(n)]
    # for i, point in enumerate(ret):
    #     if revidx[point[1]] == -1:
    #         revidx[point[1]] = i
    #
    # seg = Segtree_op(len(ret))
    # for i, r in enumerate(ret):
    #     seg.update(i,r)
    #
    # # print(revidx)
    #
    # seg.show()

    # for _ in range(q):
    #     ql, qr = getList()
    #     segl, segr = revidx[ql], revidx[qr]
    #     if segl > segr:
    #         segl, segr = segr, segl

        # print(seg.query(segl, segr)[1])
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
N, u, v = map(int, input().split())
u -= 1
v -= 1
dic = defaultdict(list)
for i in range(N-1):
  a, b = map(int, input().split())
  dic[a-1] += [b-1]
  dic[b-1] += [a-1]
dist1 = [float('inf')]*N
dist2 = [float('inf')]*N
q1 = deque([u])
q2 = deque([v])
dist1[u] = 0
dist2[v] = 0
while q1:
  e = q1.popleft()
  for p in dic[e]:
    if dist1[p]>dist1[e]+1:
      dist1[p] = dist1[e]+1
      q1 += [p]

while q2:
  e = q2.popleft()
  for p in dic[e]:
    if dist2[p]>dist2[e]+1:
      dist2[p] = dist2[e]+1
      q2 += [p]

m = -1
j = 0
for i in range(N):
  if m<dist1[i] and dist1[i]<dist2[i]:
    m = dist1[i]
    j = i

print(m+dist2[j]-dist1[j]-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
N, u, v = map(int, input().split())
u -= 1
v -= 1
dic = defaultdict(list)
for i in range(N-1):
  a, b = map(int, input().split())
  dic[a-1] += [b-1]
  dic[b-1] += [a-1]
dist1 = [float('inf')]*N
dist2 = [float('inf')]*N
q1 = deque([u])
q2 = deque([v])
dist1[u] = 0
dist2[v] = 0
while q1:
  e = q1.popleft()
  for p in dic[e]:
    if dist1[p]>dist1[e]+1:
      dist1[p] = dist1[e]+1
      q1 += [p]

while q2:
  e = q2.popleft()
  for p in dic[e]:
    if dist2[p]>dist2[e]+1:
      dist2[p] = dist2[e]+1
      q2 += [p]

m = -1
j = 0
for i in range(N):
  if m<dist1[i] and dist1[i]<dist2[i]:
    m = dist1[i]
    j = i

print(m+dist1[j]-dist2[j]+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
N, u, v = map(int, input().split())
u -= 1
v -= 1
dic = defaultdict(list)
for i in range(N-1):
  a, b = map(int, input().split())
  dic[a-1] += [b-1]
  dic[b-1] += [a-1]
dist1 = [float('inf')]*N
dist2 = [float('inf')]*N
q1 = deque([u])
q2 = deque([v])
dist1[u] = 0
dist2[v] = 0
while q1:
  e = q1.popleft()
  for p in dic[e]:
    if dist1[p]>dist1[e]+1:
      dist1[p] = dist1[e]+1
      q1 += [p]

while q2:
  e = q2.popleft()
  for p in dic[e]:
    if dist2[p]>dist2[e]+1:
      dist2[p] = dist2[e]+1
      q2 += [p]

m = 0
j = 0
for i in range(N):
  if m<dist1[i] and dist1[i]<dist2[i]:
    m = dist1[i]
    j = i

print(m+dist1[j]-dist2[j]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n, u, v = list(map(int, input().split()))
a = [[] for _ in range(n+1)]
for _ in range(n-1):
  x, y = map(int, input().split())
  a[x].append(y)
  a[y].append(x)
d = [[1,0] for _ in range(n+1)]
c = 1
for i in a[v]:
  d[i][0] = 1
  d[i][1] = c
  c += 1
b = deque(a[v])
while b:
  x = b.pop()
  for i in a[x]:
    if d[i][1] == 0:
      d[i][0] = d[x][0] + 1
      d[i][1] = d[x][1]
      b.append(i)
d[v] = [0,0]
dis = max([d[i][0] for i in range(n+1) if d[i][1]==d[u][1]])
print(dis-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n, u, v = list(map(int, input().split()))
a = [[] for _ in range(n+1)]
for _ in range(n-1):
  x, y = map(int, input().split())
  a[x].append(y)
  a[y].append(x)
d = [[0,0] for _ in range(n+1)]
c = 1
for i in a[v]:
  d[i][0] = 1
  d[i][1] = c
  c += 1
b = deque(a[v])
while b:
  x = b.pop()
  for i in a[x]:
    if d[i][1] == 0:
      d[i][0] = d[x][0] + 1
      d[i][1] = d[x][1]
      b.append(i)
d[v] = [0,0]
dis = max([d[i][0] for i in range(1,n+1) if d[i][1]==d[u][1]])
print(dis-1)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,ta,ao = inpl()
ta -= 1; ao -= 1
g = [[] for i in range(n)]
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
dist = [None] * n
dist[ao] = 0
def dfs(node):
    for v in g[node]:
        if dist[v] != None: continue
        dist[v] = dist[node] + 1
        dfs(v)
dfs(ao)
dist.sort()
print(dist[-1]-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,u,v=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]	#隣接リスト

for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)

dist_t=[ 0 for _ in range(N+1) ] #高橋君のスタート地点からの各頂点までの距離
dist_a=[ 0 for _ in range(N+1) ] #青木君のスタート地点からの各頂点までの距離

#print "al :: ",al

#高橋君のスタート地点からの各頂点までの距離
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(u)
Visit[u]=1

while q:
    fro=q.popleft()
    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1 #訪問済みに1をセット
            dist_t[to]=dist_t[fro]+1 #距離を計算
            q.append(to)

#print "dist_t :: ",dist_t

#青木君のスタート地点からの各頂点までの距離
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(v)
Visit[v]=1

while q:
    fro=q.popleft()
    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1 #訪問済みに1をセット
            dist_a[to]=dist_a[fro]+1 #距離を計算
            q.append(to)

#print "dist_a :: ",dist_a

ans=0
max_a=0
for t,a in zip(dist_t,dist_a):
    if t<a:
        ans=max(ans,t)

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,u,v=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]	#隣接リスト

for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)

dist_t=[ 0 for _ in range(N+1) ] #高橋君のスタート地点からの各頂点までの距離
dist_a=[ 0 for _ in range(N+1) ] #青木君のスタート地点からの各頂点までの距離

#print "al :: ",al

#高橋君のスタート地点からの各頂点までの距離
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(u)
Visit[u]=1

while q:
    fro=q.popleft()
    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1 #訪問済みに1をセット
            dist_t[to]=dist_t[fro]+1 #距離を計算
            q.append(to)

#print "dist_t :: ",dist_t

#青木君のスタート地点からの各頂点までの距離
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(v)
Visit[v]=1

while q:
    fro=q.popleft()
    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1 #訪問済みに1をセット
            dist_a[to]=dist_a[fro]+1 #距離を計算
            q.append(to)

#print "dist_a :: ",dist_a

ans=0
max_a=0
for t,a in zip(dist_t,dist_a):
    if t<a and max_a<a and t!=0 and a!=0:
        ans=t
        max_a=a

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,u,v=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]	#隣接リスト

for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)

dist_t=[ 0 for _ in range(N+1) ] #高橋君のスタート地点からの各頂点までの距離
dist_a=[ 0 for _ in range(N+1) ] #青木君のスタート地点からの各頂点までの距離

#print "al :: ",al

#高橋君のスタート地点からの各頂点までの距離
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(u)
Visit[u]=1

while q:
    fro=q.popleft()
    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1 #訪問済みに1をセット
            dist_t[to]=dist_t[fro]+1 #距離を計算
            q.append(to)

#print "dist_t :: ",dist_t

#青木君のスタート地点からの各頂点までの距離
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(v)
Visit[v]=1

while q:
    fro=q.popleft()
    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1 #訪問済みに1をセット
            dist_a[to]=dist_a[fro]+1 #距離を計算
            q.append(to)

#print "dist_a :: ",dist_a

ans=0
for t,a in zip(dist_t,dist_a):
    if t<=a and t!=0:
        ans=max(ans,t)
    elif t==a:
        ans=min(ans,t)

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,u,v=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]	#隣接リスト

for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)

dist_t=[ 0 for _ in range(N+1) ] #高橋君のスタート地点からの各頂点までの距離
dist_a=[ 0 for _ in range(N+1) ] #青木君のスタート地点からの各頂点までの距離

#print "al :: ",al

#高橋君のスタート地点からの各頂点までの距離
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(u)
Visit[u]=1

while q:
    fro=q.popleft()
    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1 #訪問済みに1をセット
            dist_t[to]=dist_t[fro]+1 #距離を計算
            q.append(to)

#print "dist_t :: ",dist_t

#青木君のスタート地点からの各頂点までの距離
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(v)
Visit[v]=1

while q:
    fro=q.popleft()
    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1 #訪問済みに1をセット
            dist_a[to]=dist_a[fro]+1 #距離を計算
            q.append(to)

#print "dist_a :: ",dist_a

ans=0
for t,a in zip(dist_t,dist_a):
    if t<=a and t!=0:
        ans=max(ans,t)

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,u,v=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]	#隣接リスト

for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)

dist_t=[ 0 for _ in range(N+1) ] #高橋君のスタート地点からの各頂点までの距離
dist_a=[ 0 for _ in range(N+1) ] #青木君のスタート地点からの各頂点までの距離

#print "al :: ",al

#高橋君のスタート地点からの各頂点までの距離
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(u)
Visit[u]=1

while q:
    fro=q.popleft()
    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1 #訪問済みに1をセット
            dist_t[to]=dist_t[fro]+1 #距離を計算
            q.append(to)

#print "dist_t :: ",dist_t

#青木君のスタート地点からの各頂点までの距離
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(v)
Visit[v]=1

while q:
    fro=q.popleft()
    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1 #訪問済みに1をセット
            dist_a[to]=dist_a[fro]+1 #距離を計算
            q.append(to)

#print "dist_a :: ",dist_a

ans=float("-inf")
for t,a in zip(dist_t,dist_a):
    if t<=a and t!=0:
        ans=max(ans,t)

print ans

Submission status: Wrong Answer

Solution code:
class tree:
    def __init__(self,n):
        self.edge = [set() for i in range(n)]
    def add_edge_dual(self,f,e):
        self.edge[f].add(e)
        self.edge[e].add(f)
    def add_edge_single(self,f,e):
        self.edge[f].add(e)
    def connected(self,node):
        return self.edge(node)


def dfs(graph,s):
    visited = [False for i in range(len(graph.edge))]
    distance = [-1 for i in range(len(visited))]
    visited[s] = True
    distance[s] = 0
    buf = [[s]]
    now = s
    while len(buf) != 0:
        nexts = buf[0]
        buf = buf[1:]
        temp = []
        for nex in nexts:
            for child in graph.edge[nex]:
                if visited[child] == False:
                    distance[child] = distance[nex]+1
                    temp.append(child)
                    visited[child] = True
                else:
                    continue
        if len(temp) == 0:
            continue
        else:
            buf.append(temp)
    return  distance



n,u,v = map(int,input().split())
t = tree(n)

for i in range(n-1):
    a,b = map(int,input().split())
    t.add_edge_dual(a-1,b-1)

taka = dfs(t,u-1)
aoki = dfs(t,v-1)

far = -1
aofar = -1
for i in range(n):
    if taka[i] < aoki[i]:
        if taka[i] > far:
            far = taka[i]
            aofar = aoki[i]

if far == -1:
    print(0)
elif aofar-far <= 1:
    print(far)
else:
    print(far + (aofar-far-1))

# print(taka)
# print(aoki)
# print(far,aofar)

Submission status: Wrong Answer

Solution code:
class tree:
    def __init__(self,n):
        self.edge = [set() for i in range(n)]
    def add_edge_dual(self,f,e):
        self.edge[f].add(e)
        self.edge[e].add(f)
    def add_edge_single(self,f,e):
        self.edge[f].add(e)
    def connected(self,node):
        return self.edge(node)


def dfs(graph,s):
    visited = [False for i in range(len(graph.edge))]
    distance = [-1 for i in range(len(visited))]
    visited[s] = True
    distance[s] = 0
    buf = [[s]]
    now = s
    while len(buf) != 0:
        nexts = buf[0]
        buf = buf[1:]
        temp = []
        for nex in nexts:
            for child in graph.edge[nex]:
                if visited[child] == False:
                    distance[child] = distance[nex]+1
                    temp.append(child)
                    visited[child] = True
                else:
                    continue
        if len(temp) == 0:
            continue
        else:
            buf.append(temp)
    return  distance



n,u,v = map(int,input().split())
t = tree(n)

for i in range(n-1):
    a,b = map(int,input().split())
    t.add_edge_dual(a-1,b-1)

taka = dfs(t,u-1)
aoki = dfs(t,v-1)

far = -1
aofar = -1
for i in range(n):
    if taka[i] < aoki[i]:
        if taka[i] > far:
            far = taka[i]
            aofar = aoki[i]

if aofar-far <= 1:
    print(far)
else:
    print(far + (aofar-far-1))
# print(far,aofar)

Submission status: Wrong Answer

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

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = {v}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.add(next)
    Q = tmp

# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = {u}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 < dist_from_v[next]:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.add(next)
    Q = tmp

ans = 0
for i in range(N):
    if dist_from_u[i] < dist_from_v[i]:
        ans = max(ans, dist_from_v[i]-1)
print(ans)
exit()

dst_u = dist_from_u.index(max(dist_from_u))
dist_v_dst = dist_from_v[dst_u]
ans = dist_v_dst-1
print(ans)

Submission status: Wrong Answer

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

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = {v}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.add(next)
    Q = tmp

# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = {u}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 <= dist_from_v[next]:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.add(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_v_dst = dist_from_v[dst_u]
ans = dist_v_dst-1
print(ans)

Submission status: Wrong Answer

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

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = {v}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.add(next)
    Q = tmp

# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = {u}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 < dist_from_v[next]:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.add(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_v_dst = dist_from_v[dst_u]
ans = dist_v_dst-1
print(ans)

Submission status: Wrong Answer

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

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = [v]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.append(next)
    Q = tmp

# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = [u]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 < dist_from_v[next]:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_v_dst = dist_from_v[dst_u]
ans = dist_v_dst-1
print(ans)

Submission status: Wrong Answer

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

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = [v]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.append(next)
    Q = tmp

# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = [u]
cut = None
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 >= dist_from_v[next]:
                    assert cut == None
                    cut = (cur, next)
                else:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_u_dst = max(dist_from_u)
dist_v_dst = dist_from_v[dst_u]
# print(dist_from_v)
# print(dist_from_u)
# print(cut)
assert dist_u_dst < dist_v_dst

ans = dist_v_dst
print(ans)

Submission status: Wrong Answer

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

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = [v]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.append(next)
    Q = tmp

dst_u = -1
# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = [u]
cut = None
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 >= dist_from_v[next]:
                    assert cut == None
                    cut = (cur, next)
                else:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_u_dst = max(dist_from_u)
dist_v_dst = dist_from_v[dst_u]
# print(dist_from_v)
# print(dist_from_u)
# print(cut)
assert dist_u_dst < dist_v_dst

ans = dist_v_dst-2
print(ans)