题目详情题解（0）讨论（0）提交记录（0）

AT_abc070_d.[ABC070D] Transit Tree Path

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一棵有 NN 个顶点的树。
树是一种特殊的图，如果顶点数为 NN，则边的数量为 N−1N-1，且没有环的连通图。
第 ii 条边（1≤i≤N−11\leq i\leq N-1）连接顶点 aia_i 和顶点 bib_i，距离为 cic_i。

另外，给定 QQ 个询问和一个整数 KK。

  • 对于第 jj 个询问（1≤j≤Q1\leq j\leq Q），请你求出从顶点 xjx_j 出发，经过顶点 KK，到达顶点 yjy_j 的最短路径长度。

输入格式

输入按以下格式从标准输入读入。

NN
a1a_1 b1b_1 c1c_1
a2a_2 b2b_2 c2c_2
⋮\vdots
aN−1a_{N-1} bN−1b_{N-1} cN−1c_{N-1}
QQ KK
x1x_1 y1y_1
x2x_2 y2y_2
⋮\vdots
xQx_Q yQy_Q

输出格式

对于每个询问，输出一行答案。
第 jj 行输出第 jj 个询问的答案。

输入输出样例

  • 输入#1

    5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5

    输出#1

    3
2
4

  • 输入#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

    输出#2

    5
14
22

  • 输入#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

    输出#3

    17000000000

说明/提示

限制条件

  • 3≤N≤1053\leq N\leq 10^5
  • 1≤ai,bi≤N (1≤i≤N−1)1\leq a_i,b_i\leq N\ (1\leq i\leq N-1)
  • 1≤ci≤109 (1≤i≤N−1)1\leq c_i\leq 10^9\ (1\leq i\leq N-1)
  • 给定的图保证是一棵树。
  • 1≤Q≤1051\leq Q\leq 10^5
  • 1≤K≤N1\leq K\leq N
  • 1≤xj,yj≤N (1≤j≤Q)1\leq x_j,y_j\leq N\ (1\leq j\leq Q)
  • xj≠yj (1≤j≤Q)x_j\neq y_j\ (1\leq j\leq Q)
  • xj≠K,yj≠K (1≤j≤Q)x_j\neq K, y_j\neq K\ (1\leq j\leq Q)

样例解释 1

对于给定的 33 个询问，最短路径如下：

  • 第 11 个询问：顶点 2→1→2→42\to 1\to 2\to 4，距离 1+1+1=31+1+1=3
  • 第 22 个询问：顶点 2→1→32\to 1\to 3，距离 1+1=21+1=2
  • 第 33 个询问：顶点 4→2→1→3→54\to 2\to 1\to 3\to 5，距离 1+1+1+1=41+1+1+1=4

样例解释 2

对于所有询问，最短路径都必须经过顶点 K=2K=2。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页