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:
from collections import deque

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

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

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


memov = [-1] * n
q = deque()
memov[v] = 0
q.append((v, 0))

while q:
    v_, d = q.popleft()
    for nv in g[v_]:
        if memov[nv] != -1:
            continue
        memov[nv] = d + 1
        q.append((nv, d+1))

memou = [-1] * n
q = deque()
memou[u] = 0
q.append((u, 0))

while q:
    v_, d = q.popleft()
    for nv in g[v_]:
        if memou[nv] != -1:
            continue
        if d + 1 == memov[nv]:
            memou[nv] = d + 1
            continue
        if d + 1 > memov[nv]:
            continue
        memou[nv] = d + 1
        q.append((nv, d+1))



ans = 0
max_v = -1
for i in range(n):
    if memou[i] >= ans:
        ans = memou[i]
        max_v = i
diff = memov[max_v] - memou[max_v]

if diff == 0:
    print(ans)
    exit()

if diff > 2:
    ans += (diff - 2)
    diff = 1 if diff % 2 == 1 else 2
if diff == 1:
    print(ans)
    exit()
if diff == 2:
    print(ans + 1)

Submission status: Wrong Answer

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

from collections import deque

class LCA1():
    def __init__(self, l, start):
        self.n = len(l)
        self.dep=[0]*self.n
        self.par=[[-1]*self.n for i in range(18)]

        def bfs(start):
            is_leaf = [0]*n
            que = deque()
            que.append((start, -1, 0))
            while que:
                c,p,d = que.pop()
                self.dep[v]=d
                self.par[0][v]=p
                cnt = 0
                for to in G[c]:
                    if to != p:
                        que.append((to,c,d+1))
                        cnt += 1
                if not cnt:
                    is_leaf[c] = 1
            return is_leaf

        self.is_leaf = bfs(start)

        for i in range(17):
            for j in range(self.n):
                self.par[i+1][j]=self.par[i][self.par[i][j]]

    def lca(self,a,b):
        if self.dep[a]>self.dep[b]:
            a,b=b,a
        for i in range(18):
            if (self.dep[b]-self.dep[a]) & 1<<i:
                b=self.par[i][b]
        if a==b:
            return a
        for i in range(18)[::-1]:
            if self.par[i][a]!=self.par[i][b]:
                a=self.par[i][a]
                b=self.par[i][b]
        return self.par[0][a]

    def dist(self, a,b):
        return abs(self.dep[a]-self.dep[b])

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

LCA = LCA1(G, v)
ans = 0
for i in range(n):
    if not LCA.is_leaf[i]:
        continue
    lca = LCA.lca(u, i)
    if lca == v:
        continue
    if LCA.dist(lca, u) >= LCA.dist(lca, v):
        continue
    turn = 0
    tmp = 0
    d = LCA.dist(u, lca) + LCA.dist(lca, i)
    if d != 0:
        tmp = 2*d
        aoki = d
    else:
        aoki = 0
    tak = LCA.dep[i]
    m = tak-aoki
    if m%2==1:
        tmp += 2*m -1
    else:
        tmp += 2*(m-1)
    ans = max(ans, tmp)
print(ans//2)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N,u,v = II()
A,B = Line(N-1,2)

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

def bfs(pt,v):
    n = len(pt)
    d = [-1]*n
    d[v] = 0
    q = [v]
    c = 1
    while q:
        q1 = []
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j] = c
                    q1.append(j)
        q = q1
        c += 1
    return d

pt = edges_to_pt(A,B,N)
du = bfs(pt,u-1)
dv = bfs(pt,v-1)

ans = -float('inf')
#print(du)
#print(dv)
for i in range(N):
    if du[i]>dv[i]:
        continue
    #elif len(pt[i])>=2:
    #    continue
    else:
        if len(pt[i])==1 and dv[pt[i][0]]==1:
            temp = 1
        else:
            if (du[i]-dv[i])%2==0:
                temp = dv[i]
            else:
                temp = max(0,dv[i]-1)
        ans = max(ans,temp)
        #print(i,temp)
#if ans==float('inf'):
#    ans = 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

du = [0] * N
pu = [-1] * N
q = [(u - 1, -1)]
while q :
  cur, pre = q.pop()
  for nex in vec[cur] :
    if nex != pre :
      du[nex] = du[cur] + 1
      pu[nex] = cur
      q.append((nex, cur))

dv = [0] * N
pv = [-1] * N
q = [(v - 1, -1)]
while q :
  cur, pre = q.pop()
  for nex in vec[cur] :
    if nex != pre :
      dv[nex] = dv[cur] + 1
      pv[nex] = cur
      q.append((nex, cur))

# du[u - 1] = 2
# dv[v - 1] = 2

ret = 0
for i, (u, v) in enumerate(zip(du, dv)) :
  # print(i, pu[i], pv[i])
  if u < v or (u == v and pu[i] != pv[i]) :
    if u == v :
      ret = max(ret, u)
    elif u % 2 == v % 2 :
      ret = max(ret, v - 2)
    else :
      ret = max(ret, v - 1)
print(ret)

Submission status: Wrong Answer

Solution code:
from collections import deque

N,u,v=map(int,input().split()) # u,vから1を引く必要がある
a=[[] for _ in range(N)] # 0-initial
for _ in range(N-1):
    Ai,Bi=map(int,input().split())
    a[Ai-1].append(Bi-1)
    a[Bi-1].append(Ai-1)
T=u-1;A=v-1

# 方針
# Tは，Tからの距離dTがAからの距離dA以下であるような点のうち，最もdAが大きい点を目指す。
dT=[None]*N
qT=deque()
qT.append(T);dT[T]=0
while qT:
    u=qT.popleft()
    for v in a[u]:
        if dT[v] is None:
            dT[v]=dT[u]+1
            qT.append(v)

dA=[None]*N
qA=deque()
qA.append(A);dA[A]=0
while qA:
    u=qA.popleft()
    for v in a[u]:
        if dA[v] is None:
            dA[v]=dA[u]+1
            qA.append(v)   

dis=dA[T]
'''
print(a)
print(dT)
print(dA)
'''
l=[i for i in range(N) if dT[i]<=dA[i]]
MdA=max([dA[i] for i in range(N) if i in l])
g=dA.index(MdA) # Tが目指すべきゴール

kT=dT[g] # Tが到達に要する手数
kA=dA[g] # Aが到達に要する手数
# print(g)
# print(kT,kA)
# print(dis)
if kT==kA and dis//2<=kT:
    ans=max(dis-1,0)
else:
    ans=kT+max(kA-kT-1,0)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(n, cnt):
  aoki_visited[n] = True
  aoki[n] = cnt
  for x in edge[n]:
    if aoki_visited[x] == False:
      tami(x, cnt+1)

def tami2(n, cnt):
  global ans
  choku_visited[n] = True
  if cnt < aoki[n]:
    #print("---")
    #print(n,cnt,aoki[n])
    choku[n] = cnt + (((aoki[n] - 1) - cnt) //2)*2
    for x in edge[n]:
      if choku_visited[x] == False:
        tami2(x, cnt+1)
  elif cnt == aoki[n]:
    choku[n] = cnt + ((aoki[n] - cnt) //2)*2
  ans = max(ans, choku[n])


N, u, v = IL()
ab = [IL() for _ in range(N-1)]

aoki = [0]*(N+1)
aoki_visited = [False]*(N+1)
choku = [0]*(N+1)
choku_visited = [False]*(N+1)

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

ans = 0
tami(v, 0)
tami2(u, 0)
#print(aoki)
#print(choku)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, u, v, AB):
    ans = 0
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)


    def f(start):
        s = [(start, 0)]
        d = {}
        d[start] = 0
        while s:
            c, l = s.pop()
            for n in g[c]:
                if n not in d:
                    s.append((n, l+1))
                    d[n] = l+1
        return d

    vd = f(v)
    t = u
    a = v
    s = [(t, 0)]
    d = {}
    d[t] = (vd[t] // 2) * 2
    while s:
        u, l = s.pop()
        for v in g[u]:
            if v not in d and l + 1 < vd[v]:
                s.append((v, l+1))
                tmp = vd[v] - (l+1)
                tmp = (tmp//2) * 2
                d[v] = tmp + (l+1)
    dest = (0, -1)
    for k, v in d.items():
        dest = max(dest, (v, k))

    ans = dest[0]
    # error_print(dest)
    # error_print(d)
    # error_print(vd)
    if vd[dest[1]] - dest[0] > 1:
        ans += 1
    return ans


def main():
    N, u, v = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, u, v, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import copy

n, u, v = map(int, input().split())
graph = {i + 1:[] for i in range(n)}
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
graph2 = copy.deepcopy(graph)
taka = [u]
aoki = [v]
list_t = [[u]]
list_a = [[v]]
num = 0
while list_t or list_a:
    temp_a = []
    temp_t = []
    if list_a:
        check_a = list_a.pop(0)
        for i in check_a:
            for j in graph[i]:
                if j not in taka:
                    aoki.append(j)
                    temp_a.append(j)
                    graph[j].remove(i)
        if temp_a:
            list_a.append(temp_a)
    if list_t:
        check_t = list_t.pop(0)
        for i in check_t:
            for j in graph[i]:
                if j not in aoki:
                    taka.append(j)
                    temp_t.append(j)
                    graph[j].remove(i)
        if list_t:
            list_t.append(temp_t)
list_d = []
for i in check_a:
    dis = 0
    check_list = [[i]]
    while check_list:
        check = check_list.pop(0)
        temp = []
        for j in check:
            for k in graph2[j]:
                temp.append(k)
                graph2[k].remove(j)
        if temp:
            check_list.append(temp)
            dis += 1
    list_d.append(dis)
print(max(list_d) - 1)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N,u,v = II()
A,B = Line(N-1,2)

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

def bfs(pt,v):
    n = len(pt)
    d = [-1]*n
    d[v] = 0
    q = [v]
    c = 1
    while q:
        q1 = []
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j] = c
                    q1.append(j)
        q = q1
        c += 1
    return d

pt = edges_to_pt(A,B,N)
du = bfs(pt,u-1)
dv = bfs(pt,v-1)

ans = -float('inf')
#print(du)
#print(dv)
for i in range(N):
    if du[i]>=dv[i]:
        continue
    elif len(pt[i])>=2:
        continue
    else:
        if len(pt[i])==1 and dv[pt[i][0]]==1:
            temp = 1
        else:
            if (du[i]-dv[i])%2==0:
                temp = dv[i]
            else:
                temp = max(0,dv[i]-1)
        ans = max(ans,temp)
        #print(i,temp)
#if ans==float('inf'):
#    ans = 1
print(ans)

Submission status: Wrong Answer

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

def getDist(adjList, vSt, vEn):
    numV = len(adjList)
    costs = [-1] * numV
    costs[vSt] = cost = 0
    vs = [vSt]
    while vs:
        cost += 1
        v2s = []
        for v in vs:
            for v2 in adjList[v]:
                if costs[v2] == -1:
                    costs[v2] = cost
                    v2s.append(v2)
        vs = v2s
    return costs[vEn]

# 初期状態での2人の距離
dist0 = getDist(adjL, u, v)
ans1 = dist0 - 1

def setIsOKs(adjList, vSt, dist):
    numV = len(adjList)
    costs = [-1] * numV
    costs[vSt] = cost = 0
    vs = [vSt]
    isOKs[vSt] = False
    while vs:
        cost += 1
        v2s = []
        for v in vs:
            for v2 in adjList[v]:
                if costs[v2] == -1:
                    costs[v2] = cost
                    isOKs[v2] = False
                    v2s.append(v2)
        vs = v2s
        if cost >= dist:
            break
    return

isOKs = [True] * N
setIsOKs(adjL, v, dist0//2)

def getDist2(adjList, vSt):
    numV = len(adjList)
    costs = [-1] * numV
    costs[vSt] = cost = 0
    vs = [vSt]
    while vs:
        cost += 1
        v2s = []
        for v in vs:
            for v2 in adjList[v]:
                if not isOKs[v2]: continue
                if costs[v2] == -1:
                    costs[v2] = cost
                    v2s.append(v2)
        vs = v2s

    maxC = cost-1
    vMaxC = costs.index(maxC)
    return vMaxC, maxC

# 最も遠い頂点への高橋くんからの距離
vMaxC, distT = getDist2(adjL, u)

# 最も遠い頂点への青木くんからの距離
distA = getDist(adjL, v, vMaxC)

if distT == 0:
    ans2 = 0
else:
    ans2 = distT + distA-distT-1

print(max(ans1, ans2))

Submission status: Wrong Answer

Solution code:
#F
from collections import deque
inf = float("inf")
N,u,v = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(N-1)]

rcount = [0]*N
for ab in AB:
    a,b = ab
    rcount[a-1]+=1
    rcount[b-1]+=1
    
root = []
for i in range(N):
    if rcount[i] == 1:
        root.append(i+1)
        
udist = [-1]*N
udist[u-1] = 0
d = deque(AB)
while d:
    a,b = d.popleft()
    if udist[a-1] != -1:
        udist[b-1] = udist[a-1]+1
    elif udist[b-1] != -1:
        udist[a-1] = udist[b-1]+1
    else:
        d.append([a,b])
vdist = [-1]*N
vdist[v-1] = 0
d = deque(AB)
while d:
    a,b = d.popleft()
    if vdist[a-1] != -1:
        vdist[b-1] = vdist[a-1]+1
    elif vdist[b-1] != -1:
        vdist[a-1] = vdist[b-1]+1
    else:
        d.append([a,b])


        
UVdist = udist[v-1]
flag = 1
if UVdist%2 == 1:
    flag = 0
UVmove = UVdist//2
mid = -1
for i in range(N):
    if flag == 0:
        if udist[i] == UVmove and vdist[i] == UVmove+1:
            s = i+1
        if udist[i] == UVmove+1 and vdist[i] == UVmove:
            sn = i+1
    else:
        if udist[i] == UVmove-1 and vdist[i] == UVmove+1:
            s = i+1
        if udist[i] == UVmove+1 and vdist[i] == UVmove-1:
            sn = i+1
        
sdist = [-1]*N
sdist[s-1] = 0
d = deque(AB)
while d:
    a,b = d.popleft()
    if sdist[a-1] != -1:
        sdist[b-1] = sdist[a-1]+1
    elif sdist[b-1] != -1:
        sdist[a-1] = sdist[b-1]+1
    else:
        d.append([a,b])
sndist = [-1]*N
sndist[sn-1] = 0
d = deque(AB)
while d:
    a,b = d.popleft()
    if sndist[a-1] != -1:
        sndist[b-1] = sndist[a-1]+1
    elif sndist[b-1] != -1:
        sndist[a-1] = sndist[b-1]+1
    else:
        d.append([a,b])

MAX = 0
for i in range(N):
    if MAX < sdist[i]:
        if flag == 0:
            if sdist[i] <= sndist[i]:
                MAX = max(MAX,sdist[i])
        else:
            if sdist[i] <= sndist[i]:
                MAX = max(MAX,sdist[i])
    

if flag == 1:
    print(MAX+UVmove-2)
else:
    print(MAX+UVmove)

#print(s,sn)
#print(sdist,sndist)
#print(MAX,UVmove)

Submission status: Wrong Answer

Solution code:
import collections
def main():

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

    if N == 2: return 0

    cur = []
    visited = set()
    dist0 = [0 for _ in range(N)]
    for a in range(1, N+1):
        if len(graph[a]) == 1:
            cur.append(a)
            visited.add(a)

    l = 0
    while cur:
        temp = []
        l += 1
        for a in cur:
            for b in graph[a]:
                if b != v and b not in visited:
                    dist0[b-1] = l
                    temp.append(b)
                    visited.add(b)
        cur = temp

    dist1 = [0 for _ in range(N)]
    cur = [v]
    visited = set()
    l = 0
    while cur:
        l += 1
        temp = []
        for a in cur:
            for b in graph[a]:
                if b not in visited:
                    temp.append(b)
                    visited.add(b)
                    dist1[b-1] = l
        cur = temp

    dist2 = [0 for _ in range(N)]
    cur = [u]
    visited = set()
    l = 0
    while cur:
        l += 1
        temp = []
        for a in cur:
            for b in graph[a]:
                if b not in visited:
                    temp.append(b)
                    visited.add(b)
                    dist2[b-1] = l
        cur = temp

    # print(dist0)
    # print(dist1)
    # print(dist2)

    ans = -1
    for i in range(N):
        if dist1[i] < dist2[i]:
            d = dist1[i] + dist2[i]
            if d % 2 == 0:
                d -= 1
            ans = min(ans, d)
        else:
            d = dist2[i] + dist0[i]
            if d % 2 == 0:
                d -= 1
            ans = max(ans, d)
    return ans


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

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

depth[0] = 0
que = deque()
que.append(0)
while que:
    v = que.popleft()
    for u in edges[v]:
        if depth[u] == None:
            depth[u] = depth[v] + 1
            que.append(u)
ans = abs(depth[U] - depth[V])
if ans % 2:
    flg = 0
else:
    flg = 1
print(ans + flg)

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)

A = [-1] * (N + 1)
T = [-1] * (N + 1)

stack = [u]
T[u] = 0
while stack:
  s = stack.pop()
  for g in graph[s]:
    if T[g] == -1:
      T[g] = T[s] + 1
      stack.append(g)
#print("T:", T)

stack = [v]
A[v] = 0
while stack:
  s = stack.pop()
  for g in graph[s]:
    if A[g] == -1:
      A[g] = A[s] + 1
      stack.append(g)
#print("A:", A)

answer = []
for i in range(N+1):
  if A[i] > T[i]:
    answer.append(T[i] + (A[i] - T[i]) // 2)
  elif A[i] == T[i]:
    answer.append(A[i])
print(max(answer))

Submission status: Wrong Answer

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

from collections import deque

class LCA1():
    def __init__(self, l, start):
        self.n = len(l)
        self.dep=[0]*self.n
        self.par=[[-1]*self.n for i in range(18)]
        self.is_leaf = [0]*n

        def bfs(start):
            dist = [0]*n
            is_leaf = [0]*n
            que = deque()
            que.append((start, -1, 0))
            while que:
                c,p,d = que.pop()
                dist[c] = d
                cnt = 0
                for to in G[c]:
                    if to != p:
                        que.append((to,c,d+1))
                        cnt += 1
                if not cnt:
                    is_leaf[c] = 1
            return dist, is_leaf

        self.dep, self.is_leaf = bfs(start)

        for i in range(17):
            for j in range(self.n):
                self.par[i+1][j]=self.par[i][self.par[i][j]]

    def lca(self,a,b):
        if self.dep[a]>self.dep[b]:
            a,b=b,a
        for i in range(18):
            if (self.dep[b]-self.dep[a]) & 1<<i:
                b=self.par[i][b]
        if a==b:
            return a
        for i in range(18)[::-1]:
            if self.par[i][a]!=self.par[i][b]:
                a=self.par[i][a]
                b=self.par[i][b]
        return self.par[0][a]

    def dist(self, a,b):
        return abs(self.dep[a]-self.dep[b])

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

LCA = LCA1(G, v)
ans = 0
for i in range(n):
    if not LCA.is_leaf[i]:
        continue
    lca = LCA.lca(u, i)
    if lca == v:
        continue
    if LCA.dist(lca, u) >= LCA.dist(lca, v):
        continue
    turn = 0
    tmp = 0
    d = LCA.dist(u, lca) + LCA.dist(lca, i)
    if d != 0:
        tmp = 2*d
        aoki = d
    else:
        aoki = 0
    tak = LCA.dep[i]
    m = tak-aoki
    if m%2==1:
        tmp += 2*m -1
    else:
        tmp += 2*(m-1)
    ans = max(ans, tmp)
print(ans//2)

Submission status: Wrong Answer

Solution code:
n, u, v = map(int, input().split())
edges = [[] for i in range(n+1)]
for _ in range(n-1):
    ai, bi = map(int, input().split())
    edges[ai].append(bi)
    edges[bi].append(ai)

lst = [-1 for i in range(n+1)]
lst[v] = 0
kyori = 0
tugi = edges[v]
while True:
    kyori += 1
    tugitugi = []
    atta = 0
    for node in tugi:
        if lst[node] == -1:
            atta = 1
            lst[node] = kyori
            tugitugi.extend(edges[node])
    if atta == 0:
        print(kyori-2)
        exit()
    tugi = tugitugi[:]

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(1000000)


def dfs(cur, par, g, d):
    pars[cur] = par
    for to in g[cur]:
        if to == par:
            continue
        d[to] = d[cur]+1
        md[cur] = max(md[cur], dfs(to, cur, g, d)+1)
    return md[cur]


n, u, v = map(int, input().split())
u -= 1
v -= 1
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
d = []
md = []
pars = []
f = []
for i in range(n):
    d.append(-1)
    md.append(0)
    pars.append(-1)
    f.append(False)
d[u] = 0
dfs(u, -1, g, d)
cur = v
while cur != u:
    f[cur] = True
    cur = pars[cur]
f[u] = True
res = d[v]//2
for i in range(n):
    if f[i] and d[i]*2 < d[v]:
        for to in g[i]:
            if to == pars[i] or f[to]:
                continue
            res = max(res, md[to]+1+d[v]-d[i] - 1)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
n,u,v=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

x=bfs(u-1)
y=bfs(v-1)
ans=[]
e=[]
ct0=0
for i in range(n):
  if x[i]<y[i] and x[i]!=0:
    ct0+=1
if ct0==0:
  if x[v-1]==1:
    print(0)
  else:
    print(1)
  sys.exit()
for i in range(n):
  if x[i]<y[i]:
    if abs(x[i]-y[i])%2==0:
      if x[i]%2==1:
        ans.append(y[i]-1)
      else:
        ans.append(y[i]-2)
    else:
      ans.append(y[i]-1)
print(max(ans))

Submission status: Wrong Answer

Solution code:
#1-index
import sys
input = sys.stdin.readline

from collections import deque

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

queT = deque()
queA = deque()

checkT = [-1] * (N + 1)
checkA = [-1] * (N + 1)

checkT[u] = 0
checkA[v] = 0

queT.append(u)
queA.append(v)
flag = True
while queT or queA: #どちらかが生きているとき
    tmp_lst = []
    while queT:
        tmp = queT.popleft()
        d = checkT[tmp]
        for next_ in G[tmp]:
            if checkT[next_] == -1:
                if checkA[next_] != -1:
                    flag = False
                    turn = True #高橋くんが動くとぶつかる
                    break
                checkT[next_] = d + 1
                tmp_lst.append(next_)
        if not flag:
            break
    if not flag:
        break
    for i in tmp_lst:
        queT.append(i)
    
    tmp_lst = []
    while queA:
        tmp = queA.popleft()
        d = checkA[tmp]
        for next_ in G[tmp]:
            if checkA[next_] == -1:
                if checkT[next_] != -1:
                    flag = False
                    turn = False #青木くんが動くとぶつかる
                    break
                checkA[next_] = d + 1
                tmp_lst.append(next_)
        if not flag:
            break
    if not flag:
        break
    for i in tmp_lst:
        queA.append(i)

# print (checkT)
# print (checkA)
# print (d)
# print (turn)
# print (tmp) #現在の場所
#ここまでで二人がギリギリまで近づく位置と、どちらが動いたらぶつかるかが分かる

ans = 0
check = [-1] * (N + 1)
check[tmp] = 0
stack = [tmp]
while stack:
    tmp1 = stack.pop()
    tmp_d = check[tmp1]
    flag = True
    for next_ in G[tmp1]:
        if check[next_] == -1 and checkA[next_] == -1:
            check[next_] = tmp_d + 1
            stack.append(next_)
            flag = False
    if flag:
        ans = max(ans, tmp_d)

# print (check)

if turn:
    print (d + ans)
else:
    print (d + ans - 1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

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


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
    
N, u, v = map(int, input().split())
g = Graph()
for i in range(N-1):
    a, b = map(int, input().split())
    g.add_edge(a, b, 1)
    g.add_edge(b, a, 1)
d1 = Dijkstra(g, u)
d2 = Dijkstra(g, v)

max_dist = 0
same_dist = 0

flag = d1.shortest_distance(v)%2

for i in range(1,N+1):
    s1 = d1.shortest_distance(i)
    s2 = d2.shortest_distance(i)
    print(i, s1, s2)
    if s1 < s2:
        if flag == 1:
            if s2-1 > max_dist:
                max_dist = s2-1
        else:
            if s2-1 > max_dist:
                max_dist = s2-1
    elif s1 == s2:
        if s1 < same_dist or same_dist==0:
            same_dist = s1

print(max(max_dist,same_dist))