Problem:
 Score : 400 points    Problem Statement You are given a tree with N vertices. Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N-1 edges, where N is the number of its vertices. The i -th edge (1≤i≤N-1) connects Vertices a_i and b_i , and has a length of c_i .  You are also given Q queries and an integer K . In the j -th query (1≤j≤Q) :   find the length of the shortest path from Vertex x_j and Vertex y_j via Vertex K .       Constraints  3≤N≤10^5   1≤a_i,b_i≤N (1≤i≤N-1)   1≤c_i≤10^9 (1≤i≤N-1)   The given graph is a tree.  1≤Q≤10^5   1≤K≤N   1≤x_j,y_j≤N (1≤j≤Q)   x_j≠y_j (1≤j≤Q)   x_j≠K,y_j≠K (1≤j≤Q)          Input Input is given from Standard Input in the following format:  N  a_1  b_1  c_1  :  a_{N-1}  b_{N-1}  c_{N-1}  Q  K  x_1  y_1  :  x_{Q}  y_{Q}       Output Print the responses to the queries in Q lines. In the j -th line j(1≤j≤Q) , print the response to the j -th query.        Sample Input 1 5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5      Sample Output 1 3
2
4  The shortest paths for the three queries are as follows:   Query 1 : Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4 : Length 1+1+1=3   Query 2 : Vertex 2 → Vertex 1 → Vertex 3 : Length 1+1=2   Query 3 : Vertex 4 → Vertex 2 → Vertex 1 → Vertex 3 → Vertex 5 : Length 1+1+1+1=4         Sample Input 2 7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7      Sample Output 2 5
14
22  The path for each query must pass Vertex K=2 .       Sample Input 3 10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10      Sample Output 3 17000000000

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    
    

    import sys
    from collections import deque

    def dijkstra(V, adj, root):
        que = deque()
        que.append(root)
        seen = [-1] * (N + 1)
        seen[root] = 0
        par = [0] * (N + 1)
        child = [[] for _ in range(N + 1)]
        seq = []
        while que:
            v = que.popleft()
            seq.append(v)
            for u, c in adj[v]:
                if seen[u] == -1:
                    seen[u] = seen[v] + c
                    par[u] = v
                    child[v].append(u)
                    que.append(u)
        seq.reverse()

        return seen

    N = int(input())
    V, E = N, N - 1  

    adj = [[] for _ in range(N + 1)]

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

    d = dijkstra(V, adj, root)
    for _ in range(Q):
        x, y = map(int, input().split())
        print(d[x] + d[y])


resolve()

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline

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

    que = deque()
    que.append(root)
    seen = [-1] * (N+1)
    seen[root] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u, c in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + c
                par[u] = v
                child[v].append(u)
                que.append(u)
    seq.reverse()

    for _ in range(Q):
        x, y = map(int, input().split())
        print(seen[x] + seen[y])


if __name__ == '__main__':
    main()

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline

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

    que = deque()
    que.append(root)
    seen = [-1] * (N+1)
    seen[root] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u, c in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + c
                par[u] = v
                child[v].append(u)
                que.append(u)
    seq.reverse()

    for _ in range(Q):
        x, y = map(int, input().split())
        print(seen[x] + seen[y])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    q = deque()
    Dist = [-1] * N
    q.append((K-1, K-1, 0))
    while q:
        nowN, preN, nD = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = nD
            for e, add in Edge[nowN]:
                if e != preN: q.append((e, nowN, nD + add))
    Ans = [None] * Q
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = str(Dist[x-1] + Dist[y-1])
    print("\n".join(Ans))

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    q = deque()
    Dist = [-1] * N
    q.append((K-1, K-1, 0))
    while q:
        nowN, preN, nD = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = nD
            for e, add in Edge[nowN]:
                if e != preN: q.append((e, nowN, nD + add))
    Ans = [None] * Q
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = str(Dist[x-1] + Dist[y-1])
    print("\n".join(Ans))

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque
import sys
INF = 11414191981036436433-4

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

r = [INF]*n
que = deque([k])
r[k] = 0
while que:
    v = que.popleft()
    rr = r[v]
    for w,x in g[v]:
        if r[w] == INF:
            r[w] = rr + x
            que.append(w)
            
for i in range(q):
    d,e = map(int,input().split())
    print(r[d-1] + r[e-1])

Solution (Python):
from collections import deque

N = int(input())
edges = [[]for _ in range(N+1)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    edges[a].append((b,c))
    edges[b].append((a,c))
dp = [0]*(N+1)

Q,K = map(int,input().split())
que = deque()
que.append((K,0))
path = {}
while que:
    now,cost = que.pop()
    path[now] = ""
    dp[now] = cost
    for x,c in edges[now]:
        if x not in path:
            que.append((x,cost+c))

for _ in range(Q):
    x,y = map(int,input().split())
    print(dp[x]+dp[y])

Solution (Python):
import sys
import math  
import bisect  
import queue  


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append((b, c))
        G[b].append((a, c))
    Q, K = map(int, input().split())
    K -= 1
    X = []
    Y = []
    for _ in range(Q):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        X.append(x)
        Y.append(y)

    que = queue.Queue()
    INF = 10 ** (25)
    dist = [INF for _ in range(N)]
    dist[K] = 0
    que.put(K)
    while not que.empty():
        cn = que.get()
        for nn, c in G[cn]:
            if dist[nn] > dist[cn] + c:
                dist[nn] = dist[cn] + c
                que.put(nn)

    for x, y in zip(X, Y):
        print(dist[x] + dist[y])


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

q,k = map(int,input().split())

dist = [float('inf')] * n
visited = [0] * n

dist[k-1] = 0
visited[k-1] = 1
vq = deque([k-1])

while vq:
    
    vs = vq.popleft()
    
    for ve,vc in edge[vs]:
        if visited[ve] == 1: continue
        
        dist[ve] = dist[vs] + vc
        visited[ve] = 1
        vq.append(ve)


for _ in range(q):
    x,y = map(int,input().split())
    print(dist[x-1] + dist[y-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from sys import stdin
input = stdin.readline

n = int(input())
adjacency = [[] for i in range(n+1)] 
distance = {} 
for i in range(n-1):
    line = list(map(int, input().split()))
    adjacency[line[0]].append(line[1])
    adjacency[line[1]].append(line[0])
    distance[(line[0], line[1])] = line[2]
    distance[(line[1], line[0])] = line[2]
q, k = map(int, input().split())
x = []
y = []
for i in range(q):
    line = list(map(int, input().split()))
    x.append(line[0])
    y.append(line[1])

k_distance = [-1 for i in range(n+1)] 
k_distance[k] = 0
reached = {k}
def dfs(v, d): 
    for neighbor in adjacency[v]:
        if not neighbor in reached:
            reached.add(neighbor)
            k_distance[neighbor] = d + distance[(v, neighbor)]
            dfs(neighbor, k_distance[neighbor])
    return
dfs(k, 0)
for i in range(q):
    print(k_distance[x[i]] + k_distance[y[i]])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n=int(input())
INF=9999999999
d=[INF for _ in range(n)]
g=[[] for _ in range(n)]


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

def dfs(v,p,dv):
    d[v]=dv
    for gi,c in g[v]:
        if(gi==p):
            continue
        dfs(gi,v,dv+c)

q,k=map(int,input().split())

dfs(k-1,-1,0)

for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Solution (Python):
"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(20000000)
    input = sys.stdin.readline
    N = int(input())
    AB = [[]for _ in range(N+1)]
    for i in range(N-1):
        a,b,c = map(int,input().split())
        AB[a].append((b,c))
        AB[b].append((a,c))

    Q,K = map(int,input().split())

    path = {K:""}
    dp = [0]*(N+1)
    que = deque()
    for n,c in AB[K]:
        que.append((n,c))
    while que:
        now,cost = que.pop()
        path[now]=""
        dp[now]=cost
        for n,c in AB[now]:
            if n not in path:
                que.append((n,cost+c))
    for i in range(Q):
        x,y=map(int,input().split())
        print(dp[x]+dp[y])
main()

Solution (Python):



import heapq

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

Q,K = map(int, input().split())
xy = [tuple(map(int, input().split())) for _ in range(Q)]

INF = float("inf")

dist = [INF] * N
dist[K-1] = 0
q = []
q.append((0,K-1))

while q:
    cost, curr = heapq.heappop(q)
    if cost > dist[curr]:
        continue

    for c, nxt in es[curr]:
        if dist[curr] + c < dist[nxt]:
            dist[nxt] = dist[curr] + c
            heapq.heappush(q, (dist[nxt], nxt))

for x,y in xy:
    print(dist[x-1] + dist[y-1])

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline

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

    que = deque()
    que.append(root)
    seen = [-1] * (N+1)
    seen[root] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u, c in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + c
                par[u] = v
                child[v].append(u)
                que.append(u)
    seq.reverse()

    for _ in range(Q):
        x, y = map(int, input().split())
        print(seen[x] + seen[y])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def dfs(v,p,d):
    dist[v]=d
    for nv,nd in G[v]:
        if nv==p:
            continue
        dfs(nv,v,d+nd)

N=int(input())
G=[[] for i in range(N)]
dist=[-1]*N
for i in range(N-1):
    a,b,c=map(int,input().split())
    G[a-1].append([b-1,c])
    G[b-1].append([a-1,c])
Q,K=map(int,input().split())
dfs(K-1,-1,0)
for i in range(Q):
    x,y=map(lambda x:int(x)-1,input().split())
    print(dist[x]+dist[y])

Solution (Python):
from heapq import heappush,heappop,heapify
INF=10**30
def dijkstra(G,s,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        mincost,u=heappop(que)
        if(mincost>dist[u]):
            continue
        for v,c in G[u]:
            if(dist[u]+c<dist[v]):
                dist[v]=dist[u]+c
                heappush(que,(dist[v],v))
    return dist
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    G[a-1].append([b-1,c])
    G[b-1].append([a-1,c])
Q,K=map(int,input().split())
dist=dijkstra(G,K-1,N)
for i in range(Q):
    x,y=map(lambda x:int(x)-1,input().split())
    print(dist[x]+dist[y])

Solution (Python):
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            index=0
            a,b,c=(ls[i]+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True








class SegTree:

    def __init__(self,n,init_val=0,function=lambda a,b:a+b,ide=0):
        self.n=n
        self.ide_ele=ide_ele=ide
        self.num=num=2**(n-1).bit_length()
        self.seg=seg=[self.ide_ele]*2*self.num
        self.lazy=lazy=[self.ide_ele]*2*self.num
        self.segfun=segfun=function
        
        for i in range(n):
            self.seg[i+self.num-1]=init_val
        
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.segfun(self.seg[2*i+1],self.seg[2*i+2])
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfun(self.seg[k*2+1],self.seg[k*2+2])
        
        
    def evaluate(k,l,r): 
        if lazy[k]!=0:
            node[k]+=lazy[k]
            if(r-l>1):
                lazy[2*k+1]+=lazy[k]//2
                lazy[2*k+2]+=lazy[k]//2

        lazy[k]=0
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res
    
    def find_min_index(self,p,q,m):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res


    def __str__(self):
        
        rt=self.seg[self.num-1:self.num-1+self.n]
        return str(rt)

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)


n=I()
tr=Tree(n)

q,k=LI()
v=tr.dfs(k-1)
for i in range(q):
    x,y=LI_()
    print(v[x]+v[y])

Solution (Python):
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True








class SegTree:

    def __init__(self,n,init_val=0,function=lambda a,b:a+b,ide=0):
        self.n=n
        self.ide_ele=ide_ele=ide
        self.num=num=2**(n-1).bit_length()
        self.seg=seg=[self.ide_ele]*2*self.num
        self.lazy=lazy=[self.ide_ele]*2*self.num
        self.segfun=segfun=function
        
        for i in range(n):
            self.seg[i+self.num-1]=init_val
        
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.segfun(self.seg[2*i+1],self.seg[2*i+2])
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfun(self.seg[k*2+1],self.seg[k*2+2])
        
        
    def evaluate(k,l,r): 
        if lazy[k]!=0:
            node[k]+=lazy[k]
            if(r-l>1):
                lazy[2*k+1]+=lazy[k]//2
                lazy[2*k+2]+=lazy[k]//2

        lazy[k]=0
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res
    
    def find_min_index(self,p,q,m):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res


    def __str__(self):
        
        rt=self.seg[self.num-1:self.num-1+self.n]
        return str(rt)


ans=0


class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb in self.edges[c]:
                d=1
                if type(nb) is not int:
                    nb,d=nb
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda x:x+1,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce])
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)
        



tr=Tree()

q,k=LI()
v=tr.dfs(k-1)
for i in range(q):
    x,y=LI_()
    print(v[x]+v[y])