[2026 CCPC_NC_I B] 世界树
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
给定一棵 个节点的无根树 ,节点编号为 到 ,每条边有一个整数边权(可能为负)。
定义树上两点 的距离 为它们之间的唯一简单路径上的边权之和。
现有 次查询,每次查询给定两个节点 和 ,请你计算并输出:
$$\max_{u \in T}(\operatorname{dis}(x,u)+\operatorname{dis}(y,u))$$Format
Input
第一行两个整数 (),分别表示树的节点数和查询次数。
接下来 行,每行三个整数 (, ),表示节点 与节点 之间有一条边权为 的边。保证输入构成一棵树。
接下来 行,每行两个整数 (),表示一次查询。
Output
共 行,对于每次查询,输出一行一个整数,表示所求的最大值。
Samples
4 3
1 2 1
2 3 2
2 4 -1
1 1
1 2
1 3
6
5
3
2026CCPC南昌邀请赛暨江西省赛(unofficial)
- Status
- Done
- Rule
- XCPC
- Problem
- 13
- Start at
- 2026-9-30 13:30
- End at
- 2026-9-30 17:30
- Duration
- 4 hour(s)
- Host
- Partic.
- 2