{"raw_statement":[{"iden":"problem statement","content":"You are given a tree with $N$ vertices.  \nHere, 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.  \nThe $i$\\-th edge $(1≤i≤N-1)$ connects Vertices $a_i$ and $b_i$, and has a length of $c_i$.\nYou are also given $Q$ queries and an integer $K$. In the $j$\\-th query $(1≤j≤Q)$:\n\n*   find the length of the shortest path from Vertex $x_j$ and Vertex $y_j$ via Vertex $K$."},{"iden":"constraints","content":"*   $3≤N≤10^5$\n*   $1≤a_i,b_i≤N (1≤i≤N-1)$\n*   $1≤c_i≤10^9 (1≤i≤N-1)$\n*   The given graph is a tree.\n*   $1≤Q≤10^5$\n*   $1≤K≤N$\n*   $1≤x_j,y_j≤N (1≤j≤Q)$\n*   $x_j≠y_j (1≤j≤Q)$\n*   $x_j≠K,y_j≠K (1≤j≤Q)$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$  \n$a_1$ $b_1$ $c_1$  \n$:$  \n$a_{N-1}$ $b_{N-1}$ $c_{N-1}$\n$Q$ $K$\n$x_1$ $y_1$\n$:$  \n$x_{Q}$ $y_{Q}$"},{"iden":"sample input 1","content":"5\n1 2 1\n1 3 1\n2 4 1\n3 5 1\n3 1\n2 4\n2 3\n4 5"},{"iden":"sample output 1","content":"3\n2\n4\n\nThe shortest paths for the three queries are as follows:\n\n*   Query $1$: Vertex $2$ → Vertex $1$ → Vertex $2$ → Vertex $4$ : Length $1+1+1=3$\n*   Query $2$: Vertex $2$ → Vertex $1$ → Vertex $3$ : Length $1+1=2$\n*   Query $3$: Vertex $4$ → Vertex $2$ → Vertex $1$ → Vertex $3$ → Vertex $5$ : Length $1+1+1+1=4$"},{"iden":"sample input 2","content":"7\n1 2 1\n1 3 3\n1 4 5\n1 5 7\n1 6 9\n1 7 11\n3 2\n1 3\n4 5\n6 7"},{"iden":"sample output 2","content":"5\n14\n22\n\nThe path for each query must pass Vertex $K=2$."},{"iden":"sample input 3","content":"10\n1 2 1000000000\n2 3 1000000000\n3 4 1000000000\n4 5 1000000000\n5 6 1000000000\n6 7 1000000000\n7 8 1000000000\n8 9 1000000000\n9 10 1000000000\n1 1\n9 10"},{"iden":"sample output 3","content":"17000000000"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}