Problem:


Score : 600 points

Problem Statement

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

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

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

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

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

3. Go back to step 1.

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

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

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

Constraints

2 \leq N \leq 10^5

1 \leq u,v \leq N

u \neq v

1 \leq A_i,B_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

5 4 1
1 2
2 3
3 4
3 5

Sample Output 1

2

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

Takahashi moves to Vertex 3.

Aoki moves to Vertex 2.

Takahashi moves to Vertex 5.

Aoki moves to Vertex 3.

Takahashi moves to Vertex 3.

Here, Aoki performs two moves.

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

Sample Input 2

5 4 5
1 2
1 3
1 4
1 5

Sample Output 2

1

Sample Input 3

2 1 2
1 2

Sample Output 3

0

Sample Input 4

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

Sample Output 4

5



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


Sample output:
2

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#青木を根で深さ決定
#先回りできる点のうち子の深さが最大の点
from collections import deque
n,u,v = map(int, input().split( ))

u -= 1
v -= 1
Tr =[[]for i in range(n)]

Dep = [-1]*n
Deg = [0]*n
for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai -=1
    bi -=1
    Tr[ai].append(bi)
    Tr[bi].append(ai)
    Deg[ai] += 1
    Deg[bi] += 1

Q = deque()
Dep[v] = 0
Leaf = []
Q.append(v)
while Q:
    x = Q.popleft()
    leaf = True
    for y in Tr[x]:
        if Dep[y] == -1:
            Dep[y] = Dep[x] + 1
            Q.append(y)
            leaf = False
    if leaf:
        Leaf.append(x)
Parent = [-1]*n
Parent[v] = v
for i in range(n):
    for j in Tr[i]:
        if Dep[j]<Dep[i]:
            Parent[i] = j

Path= []
tmp = u
while tmp !=v:
    Path.append(tmp)
    tmp = Parent[tmp]
Q = deque()
Dep_max = [-1]*n
for l in Leaf:
    Q.append(l)
    Dep_max[l] = Dep[l]

while Q:
    x = Q.popleft()
    y = Parent[x]
    if y!=v:
        Deg[y] -= 1
    Dep_max[y] = max(Dep_max[y],Dep_max[x])
    if Deg[y]-1 == 0 and y!=v:
        Q.append(y)
        Deg[y]-=1
D_m_path = []
lp = len(Path)
for i in range(lp):
    D_m_path.append(Dep_max[Path[i]])
ans = max(D_m_path[:(lp+1)//2])
print(ans-1)

Submission status: Accepted

Solution code:
import copy
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

N,U,V = map(int, input().split())
d = [set() for _ in range(N+1)]
dps = [0 for _ in range(N+1)]
dpss = [0 for _ in range(N+1)]
vs = set()
r = {}

def it(v, p, depth, ps):
    for u in d[v]:
        if u == p:
            continue
        dps[u] = depth
        if u == V:
            r["p"] = copy.deepcopy(ps)
            continue
        ps.add(u)
        it(u, v, depth+1,ps)
        ps.remove(u)
        vs.add(u)

def it2(v, p, depth):
    for u in d[v]:
        if u == p:
            continue
        if u not in vs:
            continue
        if dps[v] >= depth-1 and u not in r["p"]:
            continue
        dpss[u] = depth
        it2(u, v, depth+1)



for _ in range(N-1):
    a, b = [int(x) for x in input().split()]
    d[a].add(b)
    d[b].add(a)

vs.add(U)
it(U, -1, 1, set([U]))
it2(V, -1, 1)
print(max(dpss)-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from collections import deque

def main():
    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)

    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

    a, is_leaf = bfs(v)
    b, _ = bfs(u)

    ans = 0
    for i in range(n):
        if not is_leaf[i]:
            continue
        if b[i] >= a[i]:
            continue
        tmp = 0
        d = b[i]
        if d != 0:
            tmp = 2*d
            aoki = d
        else:
            aoki = 0
        tak = a[i]
        m = tak-aoki
        if m%2==1:
            tmp += 2*m -1
        else:
            tmp += 2*(m-1)
        ans = max(ans, tmp)
    print(ans//2)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]


def bfs(s,n,g):
    went = [False]*n
    dis = [0]*n
    que = deque([])
    que.append(s)
    went[s] = True
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if went[g[go][i]]:
                continue
            dis[g[go][i]] = dis[go] + 1
            went[g[go][i]] = True
            que.append(g[go][i])
    return dis

def main():
    n,u,v = inpm()
    g = [[] for _ in range(n)]
    g1 = [[] for _ in range(n)]
    ab = []
    for _ in range(n-1):
        a,b = inpm()
        a -= 1
        b -= 1
        g[b].append(a)
        g[a].append(b)
        ab.append((a,b))
    dis = bfs(u-1,n,g)
    path = [v-1]
    que = deque([])
    que.append(v-1)
    d = dis[v-1]-1
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] == d:
                d -= 1
                path.append(g[go][i])
                que.append(g[go][i])
    ans = int(len(path)/2)-1
    path.reverse()
    for i in range(n-1):
        if (ab[i][0],ab[i][1]) == (path[ans],path[ans+1]) or (ab[i][1],ab[i][0]) == (path[ans],path[ans+1]):
            continue
        g1[ab[i][0]].append(ab[i][1])
        g1[ab[i][1]].append(ab[i][0])
    dis1 = bfs(path[ans],n,g1)
    x = ans+max(dis1)
    if len(path)%2==1:
        x+=1    
    print(x)




if __name__ == "__main__":
    main()

Submission status: Accepted

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

u -= 1
v -= 1
G = [set() for _ in range(N)]
for a, b in AB:
    G[a - 1].add(b - 1)
    G[b - 1].add(a - 1)


du = [-1] * N
du[u] = 0
q = set([u])
while q:
    i = q.pop()
    for j in G[i]:
        if du[j] == -1:
            du[j] = du[i] + 1
            q.add(j)

dv = [-1] * N
dv[v] = 0
q = set([v])
while q:
    i = q.pop()
    for j in G[i]:
        if dv[j] == -1:
            dv[j] = dv[i] + 1
            q.add(j)

ans = 0
for i in range(N):
    if du[i] < dv[i]:
        ans = max(ans, dv[i])
ans -= 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N,t,a=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)
    
#print(L)

Q=[[t,0]]
C1=[-1 for i in range(N+1)]
for i in range(10**6):
    if i==len(Q):
        break
    if C1[Q[i][0]]==-1:
        C1[Q[i][0]]=Q[i][1]
        if Q[i][0]!=a:
            for j in L[Q[i][0]]:
                if C1[j]==-1:
                    Q.append([j,Q[i][1]+1])
#print(C1)

Q=[[a,0]]
C2=[-1 for i in range(N+1)]
for i in range(N+1):
    if C1[i]==-1:
        C2[i]=-2
#print(C2)
for i in range(10**6):
    if i==len(Q):
        break
    if C2[Q[i][0]]==-1:
        C2[Q[i][0]]=Q[i][1]
        for j in L[Q[i][0]]:
            if C2[j]==-1:
                Q.append([j,Q[i][1]+1])
#print(C1)
#print(C2)
ANS=0
for i in range(N+1):
    if C1[i]<C2[i] and C2[i]>ANS:
        ANS=C2[i]
print(ANS-1)

Submission status: Accepted

Solution code:
n,u,v=[int(j) for j in input().split()]
u,v=u-1,v-1
l=[[] for i in range(n)]
for i in range(n-1):
    a,b=[int(j)-1 for j in input().split()]
    l[a].append(b)
    l[b].append(a)
k=[10**18 for i in range(n)]
from collections import deque
q=deque([u])
k[u]=0
s=set()
while q:
    p=q.popleft()
    s.add(p)
    for i in l[p]:
        if i not in s:
            q.append(i)
            k[i]=k[p]+1

k2=[10**18 for i in range(n)]
from collections import deque
q=deque([v])
k2[v]=0
s=set()
while q:
    p=q.popleft()
    s.add(p)
    for i in l[p]:
        if i not in s:
            q.append(i)
            k2[i]=k2[p]+1
ll=[]
ans=0
for i in range(n):
    if k[i]<=k2[i]:
        ll.append(i)
        ans=max(ans,k2[i])


print(ans-1)

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.readline
from collections import deque
N, u, v = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
v-=1
u-=1
que = deque([v])
par = [-1]*N
depth = [-1]*N
depth[v] = 0
while que:
    i = que.popleft()
    d = depth[i]
    for nv in G[i]:
        if depth[nv]>=0:
            continue
        depth[nv] = d+1
        par[nv] = i
        que.append(nv)
d = depth[u]
now = u
m = 0
que = deque([now])
while que:
    i = que.pop()
    m = max(m, depth[i])
    for nv in G[i]:
        if depth[nv]<depth[i]:
            continue
        que.append(nv)
for i in range(d//2):
    pp = par[now]
    que = deque([pp])
    while que:
        i = que.pop()
        m = max(m, depth[i])
        for nv in G[i]:
            if depth[nv]<depth[i] or nv == now:
                continue
            que.append(nv)
    now = pp
print(m-1)

Submission status: Accepted

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


def dfs(node, dist):
    for children in tree[node]:
        if not visited[children]:
            visited[children] = True
            dist[children] = dist[node] + 1
            dfs(children, dist)


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)
dist_u = [0] * N
dist_v = [0] * N
visited = [False] * N
visited[u] = True
dfs(u, dist_u)
visited = [False] * N
visited[v] = True
dfs(v, dist_v)

max_move_same = -1
max_move = 0
for i in range(N):
    if dist_u[i] == dist_v[i]:
        if max_move_same == -1 or max_move_same > dist_v[i]:
            max_move_same = dist_v[i]
    if dist_u[i] < dist_v[i]:
        max_move = max(max_move, dist_v[i] - 1)

print(max(max_move_same, max_move))

Submission status: Accepted

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def bitlist(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

#a = list(map(int, input().split()))

n,a,b = list(map(int, input().split()))
es = [[] for i in range(n+1)]

for i in range(n-1):
    p,q = list(map(int, input().split()))
    es[p].append(q)
    es[q].append(p)

dista = [9999999 for i in range(n+1)]
distb = [9999999 for i in range(n+1)]



dista[a]=0
distb[b]=0

queue = [[a,0]]
snum = 0
while(True):
    if(snum==len(queue)):
        break
    nowel = queue[snum]
    nowv = nowel[0]
    #print(nowv)
    nowdist = nowel[1]
    #print(nowdist)
    elist = es[nowv]
    for j in range(len(elist)):
        if(dista[elist[j]]>9999990):
            queue.append([elist[j],nowdist+1])
            dista[elist[j]] = nowdist+1
    snum+=1
#print(dista)


queue = [[b,0]]
snum = 0
while(True):
    if(snum==len(queue)):
        break
    nowel = queue[snum]
    nowv = nowel[0]
    #print(nowv)
    nowdist = nowel[1]
    #print(nowdist)
    elist = es[nowv]
    for j in range(len(elist)):
        if(distb[elist[j]]>9999990):
            queue.append([elist[j],nowdist+1])
            distb[elist[j]] = nowdist+1
    snum+=1
#print(distb)

acan = [0 for i in range(n+1)]

for ii in range(n):
    i = ii+1
    if(dista[i] < distb[i]):
        acan[i]=1

maxb = 0
k = 0

for ii in range(n):
    i = ii+1
    if(maxb < distb[i] and acan[i]==1):
        maxb = distb[i]
        k = i

if(abs(dista[k] - distb[k])%2 == 0):
    print(maxb-1)
    #print("0:",k)
else:
    print(maxb-1)
    #print("1",k)

Submission status: Accepted

Solution code:
n,u,v=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]
data=[[] for i in range(n+1)]
for a,b in ab:
    data[a].append(b)
    data[b].append(a)
flag=[-1]*(n+1)
que=[u]
flag[u]=0
cnt=1
while que:
    h=[]
    for x in que:
        for y in data[x]:
            if flag[y]==-1:
                flag[y]=cnt
                h.append(y)
    cnt+=1
    que=h
flag_2=[-1]*(n+1)
que=[v]
flag_2[v]=0
cnt=1
start=0
ans=0
if flag[v]<=2:
    start=v
else:
    while que:
        h=[]
        for x in que:
            for y in data[x]:
                if flag_2[y]==-1:
                    flag_2[y]=cnt
                    h.append(y)
                    if flag[y]-flag_2[y]<=2:
                        ans=flag_2[y]
                        start=y
                        break
            else:
                continue
            break
        else:
            cnt+=1
            que=h
            continue
        break
que=[start]
if flag[v]%2==0:
    ans+=1
    h=[]
    for x in que:
        for y in data[x]:
            if flag_2[y]==-1 and flag[y]==ans:
                flag_2[y]=ans
                h.append(y)
    que=h
while que:
    ans+=1
    h=[]
    for x in que:
        for y in data[x]:
            if flag_2[y]==-1 and ans>flag[y]:
                flag_2[y]=ans
                h.append(y)
    que=h
print(ans-2)

Submission status: Accepted

Solution code:
N, u, v = map(int, input().split())
ABs = [tuple(map(int, input().split())) for _ in range(N - 1)]

def BFS(K, edges, N):
    roots = [[] for _ in range(N)]
    for a, b in edges:
        roots[a-1] += [(b-1)]
        roots[b-1] += [(a-1)]
    dist = [-1]*N
    stack = []
    stack.append(K)
    dist[K] = 0
    while stack:
        label = stack.pop(-1)
        for i in roots[label]:
            if dist[i] == -1:
                dist[i] = dist[label] + 1
                stack += [i]
    return dist

U = BFS(u - 1, ABs, N)
V = BFS(v - 1, ABs, N)

max_ = 0
for a, b in zip(U, V):
    if a < b:
        max_ = max(max_, b - 1)

print(max_)

Submission status: Accepted

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

# T[node] = [parent, depth, [children]]
T = [[] for i in range(N)]
search = [(v, -1, 0)]
searched = [False for i in range(N)]
while len(search) > 0:
	s = search.pop()
	node = s[0]
	parent = s[1]
	depth = s[2]
	searched[node] = True
	children = []
	for n in E[node]:
		if not searched[n]:
			search.append((n, node, depth+1))
			children.append(n)
	T[node] = [parent, depth, children]

root2 = u
d_u = T[u][1]
for i in range((d_u - 1) // 2):
	root2 = T[root2][0]
max_depth = -1
leaf = -1
search = [(root2, 0)]
while len(search) > 0:
	s = search.pop()
	node = s[0]
	depth = s[1]
	children = T[node][2]
	for c in children:
		search.append((c, depth+1))
	if len(children) == 0 and max_depth < depth:
		max_depth = depth
		leaf = node
if d_u == 1:
	print(0)
else:
	print(T[leaf][1] - 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,x,y=map(int,input().split())
    x-=1; y-=1

    E=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)
        E[v].append(u)

    # x から y への path を作る(depthも)
    Q=[(x,-1)]
    prev=[None]*n
    prev[x]=-1
    depth=[None]*n
    depth[x]=0
    while(Q):
        v,p=Q.pop()
        for nv in E[v]:
            if(nv==p): continue
            prev[nv]=v
            depth[nv]=depth[v]+1
            Q.append((nv,v))

    z=y
    path=[]
    while(z!=-1):
        path.append(z)
        z=prev[z]

    # y からの depth
    Q=[(y,-1)]
    depth2=[None]*n
    depth2[y]=0
    while(Q):
        v,p=Q.pop()
        for nv in E[v]:
            if(nv==p): continue
            depth2[nv]=depth2[v]+1
            Q.append((nv,v))

    k=len(path)
    s,t=path[k//2-1],path[k//2]

    Q=[(x,-1)]
    can=[0]*n
    can[x]=1
    while(Q):
        v,p=Q.pop()
        for nv in E[v]:
            if(nv==p): continue
            if((v,nv)==(s,t) or (v,nv)==(t,s)): continue
            can[nv]=1
            Q.append((nv,v))

    d1,z=max((depth2[v],v) for v in range(n) if(can[v]))
    d2=depth[z]
    # print(d1,d2)
    # if((d1+d2)&1):
    #     d1-=1

    print(d1-1)
resolve()

Submission status: Accepted

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

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

q=deque([(v,0)])
T=[-1]*N
A=[-1]*N

while q:
    p,x=q.pop()
    A[p]=x
    for to in L[p]:
        if A[to]==-1:
            q.append((to,x+1))

q=deque([(u,0)])
while q:
    p,x=q.pop()
    T[p]=x
    for to in L[p]:
        if T[to]==-1 and A[to]>x+1:
            q.append((to,x+1))


Tcan=[i for i,x in enumerate(T) if x!=-1]
cnt,gi=max([(A[i], i) for i in Tcan]+[(0,0)])
if cnt<=1:
    print(0)
    exit()
print(A[gi]-1)

Submission status: Accepted

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: Accepted

Solution code:
from collections import deque
N, U, V = map(int, input().split())
U -= 1
V -= 1
tree = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)


def get_rank(v):
    rank = [-1] * N
    next_v = deque([v])
    rank[v] = 0
    while next_v:
        node = next_v.popleft()
        r = rank[node]
        for i in tree[node]:
            if rank[i] != -1:
                continue
            rank[i] = r + 1
            next_v.append(i)
    return rank


takahashi = get_rank(U)
aoki = get_rank(V)
ans = 0
for x, y in zip(takahashi, aoki):
    if x <= y:
        ans = max(ans, y-1)

print(ans)

Submission status: Accepted

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

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

du = dijkstra(g,N,u-1)
dv = dijkstra(g,N,v-1)
d = []
for i in range(N):
    if dv[i]-du[i]>=0:
        d.append(dv[i])
ans = max(d)-1
print(ans)

Submission status: Accepted

Solution code:
N,u,v=[int(i) for i in input().split(" ")]
u-=1
v-=1
graph={}
for i in range(N-1):
    A,B=[int(j) for j in input().split(" ")]
    if A-1 in graph:
        d=graph[A-1]
        d.append(B-1)
        graph[A-1]=d
    else:
        graph[A-1]=[B-1]
    if B-1 in graph:
        d=graph[B-1]
        d.append(A-1)
        graph[B-1]=d
    else:
        graph[B-1]=[A-1]

dist_takahashi=[-1 for i in range(N)]
dist_takahashi[u]=0
next=[u]
d=1
while -1 in dist_takahashi:
    _next=[]
    for n in next:
        nodes=graph[n]
        for i in nodes:
            if dist_takahashi[i]==-1:
                _next.append(i)
    for n in _next:
        dist_takahashi[n]=d
    next=_next
    d+=1

dist_aoki=[-1 for i in range(N)]
dist_aoki[v]=0
next=[v]
d=1
while -1 in dist_aoki:
    _next=[]
    for n in next:
        nodes=graph[n]
        for i in nodes:
            if dist_aoki[i]==-1:
                _next.append(i)
    for n in _next:
        dist_aoki[n]=d
    next=_next
    d+=1


retval=0

for i in range(N):
    if dist_aoki[i]<dist_takahashi[i]:
        continue

    retval=max(retval,dist_aoki[i]-1)


print(retval)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
def prime_decomposition(n): #素因数分解
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

def make_divisors(n): #約数列挙
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
#########################
n,w,p = map(int,input().split())

edge = [[] for i in range(n)]
dg = 10**7
#隣接リスト edge[i]:[コスト,行先]
for i in range(n-1):
    x,y = map(int,input().split())
    z = 1
    x -= 1
    y -= 1
    edge[x].append(dg + y)
    edge[y].append(dg + x)

import heapq



#edge[i]:[ cost1*dg + j1,...] 
"""
for _ in [0]*m:
    u,v,w = map(int,input().split())
    edge[u-1].append(w*dg+v-1)
    #edge[v-1].append(w*dg+u-1)
"""

#dijkstra
# d : minimum distance from s
s = w-1
ss = p-1
d = [-1]*n
d[s] = 0

d2 = [-1]*n
d2[ss] = 0
edgelist = []
edgelist2 = []
for e in edge[s]:
    heapq.heappush(edgelist,e)

for e in edge[ss]:
    heapq.heappush(edgelist2,e)
    

while len(edgelist):
    minedge = heapq.heappop(edgelist)
    v,c = minedge%dg,minedge//dg
    if d[v] >= 0:
        continue
    d[v] = c
    for e in edge[v]:
        vNext = e%dg
        if d[vNext]:
            heapq.heappush(edgelist, (e//dg+d[v])*dg + vNext)

while len(edgelist2):
    minedge = heapq.heappop(edgelist2)
    v,c = minedge%dg,minedge//dg
    if d2[v] >= 0:
        continue
    d2[v] = c
    for e in edge[v]:
        vNext = e%dg
        if d2[vNext]:
            heapq.heappush(edgelist2, (e//dg+d2[v])*dg + vNext)


co = 0
for i in range(n):
    if co < d2[i] and d2[i]-d[i]>=0:
        co = d2[i]

print(co-1)

Submission status: Accepted

Solution code:
from collections import deque
N,u,v = map(int,input().split())#u=高橋 v=青木
u -= 1
v -= 1 #0-indexed
cango = [[] for i in range(N)]
#辺入力
for i in range(N-1):
    A,B = map(int,input().split())
    cango[A-1].append(B-1)#0-indexed
    cango[B-1].append(A-1)
#BFS
pres = [-1]*N#直前に来た頂点 
fromaoki = [-1]*N
fromaoki[v] = 0
went = [False]*N
queue =deque()#append,popleft
queue.append([v,0])#[場所,前の頂点]
went[v] = True#青木スタート
while queue:
    curpos,prespos = queue.popleft()
    pres[curpos] = prespos
    for togo in cango[curpos]:
        if not went[togo]:
            went[togo] = True
            fromaoki[togo] = fromaoki[curpos]+1
            queue.append([togo,curpos])
#高橋-青木ルート検索
route=[]#[高橋(u)-ルート-青木(v)]こともある
tadori = u
while tadori!=v:
    route.append(tadori)
    tadori = pres[tadori]
route.append(v)

nekko = route[len(route)//2-1] #高橋が行けるギリギリの場所
cantgo = route[len(route)//2]
cango[nekko].remove(cantgo)
cango[cantgo].remove(nekko)

#根っこからの長さ探索
def BFS(start):
    dist = [-1]*N
    dist[start] = 0
    went = [False]*N
    queue =deque()#append,popleft
    queue.append(start)
    went[start] = True
    while queue:
        curpos = queue.popleft()
        for togo in cango[curpos]:
            if not went[togo]:
                went[togo] = True
                dist[togo] = dist[curpos]+1
                queue.append(togo)
    return dist

fromnekko = BFS(nekko)
maxdist = max(fromnekko)
maxpos = fromnekko.index(maxdist)
print(fromaoki[maxpos]-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush, heappop
inf = float('inf')
mod = 10**9 + 7

# ダイクストラ法 計算量O(ElogV)
# [引数]: 隣接リスト, 始点
class Dijkstra:
    def __init__(self, to:list, start:int):
        self.N = len(to)
        self.to = [s[:] for s in to]
        self.start = start
        self.dist = [inf] * self.N
        self.dist[start] = 0
        # cnt : 最短経路の数
        # self.cnt = [0] * self.N
        # self.cnt[start] = 1
        self.pq = [(self.dist[start], start)]

    # distを更新
    def update(self) -> None:
        while self.pq:
            _, v = heappop(self.pq)
            for nv, w in self.to[v]:
                if self.dist[nv] > self.dist[v] + w:
                    self.dist[nv] = self.dist[v] + w
                    heappush(self.pq, (self.dist[nv], nv))
                # if self.dist[nv] == self.dist[v] + w:
                #     self.cnt[nv] += self.cnt[v]
                #     self.cnt[nv] %= mod

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

T = Dijkstra(to, u)
T.update()
A = Dijkstra(to, v)
A.update()

adopt = 0
for d1, d2 in zip(T.dist, A.dist):
    if d1 > d2:
        continue
    adopt = max(adopt, d2)

ans = adopt - 1
print(ans)