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

Solution (Python):
n, u, v = map(int,input().split())
edges = [[] for i in range(n)]


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


ha = [0 for i in range(n)]
def dfs(v):
    d= [0] * n
    q=[v]
    visited = [0] * n
    while q:
        v=q.pop()
        visited[v] = 1
        visited.append(v)
        c = True
        for i in edges[v]:
            if not visited[i]:
                d[i] = d[v] + 1
                q.append(i)
                c = False
        if c:
            ha[v] = 1
    return d,ha

df_nige , ha= dfs(u-1)
df_oi ,ha =dfs(v-1)

moku = -1
dfsa_mo = []
for i in range(n):
    kos =  df_oi[i] - df_nige[i] 
    dfsa_mo.append(kos)



ako = []

for i in range(n):
    dfsa = dfsa_mo[i]
    moku = i
    if dfsa > 0 and ha[i] == 1:
        if dfsa%2 == 0:
            if dfsa > 3:
                ans = df_nige[moku] + dfsa - 2 + 1
            elif dfsa == 2:
                ans = df_nige[moku] + 1
            else:
                ans = df_nige[moku]
        else:
            if dfsa == 1:
                ans = df_nige[moku]
            else:
                ans = df_nige[moku] + dfsa - 3 + 2
        
        ako.append(ans)

    else:
        ako.append(-1)


gege = max(ako)
print(gege)

Solution (Python):
import sys
input=sys.stdin.readline
from collections import deque

class LCA:
    def __init__(self,v,Edges,root=0):
        self.v=v
        self.Edges=Edges
        self.maxLog=18
        self.Parent=[[-1]*v for _ in range(self.maxLog+1)]
        self.Depth=[0]*v
        self.__bfs(root)
        for i in range(self.maxLog):
            for j in range(v):
                if self.Parent[i][j]!=-1:
                    self.Parent[i+1][j]=self.Parent[i][self.Parent[i][j]]
    def __bfs(self,root):
        Visited=[False]*self.v
        Visited[root]=True
        q=deque([root])
        while q:
            fr=q.pop()
            for to in self.Edges[fr]:
                if Visited[to]:
                    continue
                self.Parent[0][to]=fr
                self.Depth[to]=self.Depth[fr]+1
                Visited[to]=True
                q.append(to)
    def lca(self,a,b):
        if self.Depth[a]>self.Depth[b]:
            a,b=b,a
        for i in range(self.maxLog):
            if (self.Depth[b]-self.Depth[a])&(1<<i):
                b=self.Parent[i][b]
        if a==b:
            return b
        for i in reversed(range(self.maxLog-1)):
            if self.Parent[i][a]!=self.Parent[i][b]:
                a=self.Parent[i][a]
                b=self.Parent[i][b]
        return self.Parent[0][a]
    def dist(self,a,b):
        lca=self.lca(a,b)
        return self.Depth[a]+self.Depth[b]-2*self.Depth[lca]

def main():
    n,u,v=map(int,input().split())
    u-=1; v-=1
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        x,y=map(lambda i: int(i)-1,input().split())
        Edges[x].append(y)
        Edges[y].append(x)
    L=[]
    for i in range(n):
        if len(Edges[i])==1:
            L.append(i)
    lca=LCA(n,Edges,v)
    dist=lca.dist(u,v)
    ans=dist//2
    for l in L:
        m=lca.lca(u,l)
        if lca.dist(u,m)>=lca.dist(v,m):
            continue
        d_u=lca.dist(u,l)
        d_v=lca.dist(v,l)
        d=d_v-d_u
        cnt=d-1
        ans=max(ans,d_u+cnt)
    print(ans)
    
if __name__=='__main__':
    main()

Solution (Python):
n,u,v=map(int,input().split())
anss=0
u-=1
v-=1
d=[[]for _ in range(n)]
inf=float('inf')
aoki=[inf]*n
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  d[a].append(b)
  d[b].append(a)
Q=d[v]
aoki[v]=0
dis=1
visited={v}
while Q:
  P=[]
  for i in Q:
    visited.add(i)
    for j in d[i]:
      if j not in visited:P.append(j)
    aoki[i]=dis
  dis+=1
  Q=P
Q=d[u]
chokudai=[-1]*n
chokudai[u]=0
dis=1
visited={u}
point=-1
while Q:
  P=[]
  for i in Q:
    visited.add(i)
    for j in d[i]:
      if aoki[j]<=dis+1:
        if aoki[j]==dis+1:anss=1
        if point<0:point=i
        continue
      if j not in visited:P.append(j)
    chokudai[i]=dis
  dis+=1
  Q=P
Q=d[point]
dis=chokudai[point]+1
visited={point}
while Q:
  P=[]
  for i in Q:
    visited.add(i)
    if chokudai[i]==-1:continue
    chokudai[i]=max(dis,chokudai[i])
    for j in d[i]:
      if j not in visited:P.append(j)
  dis+=1
  Q=P
ans=0
for i in range(n):
  if aoki[i]>chokudai[i]:ans=max(ans,chokudai[i])
print(ans+anss)

Solution (Python):
from collections import deque


def solve(n, u, v, edge_list):
    
    g = [[] for i in range(n)]
    for a, b in edge_list:
        g[a].append(b)
        g[b].append(a)

    
    parent = [0] * n
    depth = [0] * n
    parent[v] = -1
    queue = deque([v])
    while len(queue) > 0:
        p = queue.popleft()
        for q in g[p]:
            if parent[p] != q:
                parent[q] = p
                depth[q] = depth[p] + 1
                queue.append(q)

    
    temp_list = [[i, -depth[i]] for i in range(n)]
    temp_list = list(sorted(temp_list, key=lambda x: x[1]))
    run_list = [temp_list[i][0] for i in range(n)]
    max_children_depth = depth.copy()
    for i in run_list[:-1]:
        max_children_depth[parent[i]] = max(max_children_depth[parent[i]], max_children_depth[i])
    
    
    du = depth[u]
    up = u
    res = 0
    if du > 2:
        for _ in range((du - 1) // 2):
            up = parent[up]
            res += 1
    res += max_children_depth[up] - depth[up]
    if du % 2 == 0:
        res += 1
    return res


def main():
    n, u, v = map(int, input().split())
    edge_list = [[0, 0] for _ in range(n - 1)]
    for i in range(n - 1):
        a, b = map(int, input().split())
        edge_list[i][0] = a - 1
        edge_list[i][1] = b - 1
    u -= 1
    v -= 1
    res = solve(n, u, v, edge_list)
    print(res)


def test():
    assert solve(5, 3, 0, [[0, 1], [1, 2], [2, 3], [2, 4]]) == 2
    assert solve(5, 3, 4, [[0, 1], [0, 2], [0, 3], [0, 4]]) == 1
    assert solve(2, 0, 1, [[0, 1]]) == 0


if __name__ == "__main__":
    test()
    main()

Solution (Python):
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]-1
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)

Solution (Python):
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]-1)
    else:
      ans.append(y[i]-1)
print(max(ans))

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

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

dist_r = [0] * n
dist_t = [0] * n

def dfs(v, p, dist):
    dist_r[v] = dist
    ret = 0
    for nv in g[v]:
        if nv == p: continue
        ret = max(ret, dfs(nv, v, dist+1))
    dist_t[v] = ret
    return ret + 1

dfs(A, -1, 0)

init_dist = dist_r[T]
v = T
d1 = 0
d2 = init_dist
while init_dist - dist_r[v] < dist_r[v]:
    if d1 < dist_t[v]:
        d1 = dist_t[v]
        d2 = dist_r[v]
    for nv in g[v]:
        if dist_r[v] > dist_r[nv]:
            v = nv
            break

print(d1+d2-1)

Solution (Python):
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

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        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))

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
minans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

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

def make_tree_dfs(n,d):
    D[n]=d
    tmp=0
    f=True
    for gi in G[n]:
        if D[gi]==-1:
            f=False
            tmp=max(tmp,make_tree_dfs(gi,d+1))
    if f: tmp=d
    maxD[n]=tmp
    return tmp

make_tree_dfs(v,0)
sdis=D[u]

def good_dfs(v,d,sdis):
    f=True
    for gi in G[v]:
        if D[gi]==d-1 and d-1>sdis-(d-1):
            return good_dfs(gi,d-1,sdis)
    return (maxD[v],d)

gd,orid=good_dfs(u,D[u],sdis)
k=orid-(sdis-orid)
print(gd-orid+(sdis-orid)+k-1)

Solution (Python):


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)

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy


from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    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()

Solution (Python):
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)

Solution (Python):
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)
    


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])


Q=[[a,0]]
C2=[-1 for i in range(N+1)]
for i in range(N+1):
    if C1[i]==-1:
        C2[i]=-2

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])


ANS=0
for i in range(N+1):
    if C1[i]<C2[i] and C2[i]>ANS:
        ANS=C2[i]
print(ANS-1)

Solution (Python):
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)

Solution (Python):
import sys

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)

Solution (Python):
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))

Solution (Python):
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)

    
    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



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]
    
    nowdist = nowel[1]
    
    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



queue = [[b,0]]
snum = 0
while(True):
    if(snum==len(queue)):
        break
    nowel = queue[snum]
    nowv = nowel[0]
    
    nowdist = nowel[1]
    
    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


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)
    
else:
    print(maxb-1)

Solution (Python):
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)

Solution (Python):
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_)

Solution (Python):
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 = [[] 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)

Solution (Python):
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)

    
    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]

    
    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-1)
resolve()

Solution (Python):
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)

Solution (Python):

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)

Solution (Python):
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)