#P4363. Path
Path
题目描述
给定一棵 个结点的无根树,每条边有正整数权值。
每次询问给出结点 和正整数 。选择 条简单路径,要求至少一条路径经过 ,并使这些路径覆盖的边的权值之和最大。若多条路径经过同一条边,只计一次该边权值。
输入格式
第一行两个整数 ,分别表示结点数和询问数。
接下来 行,每行三个整数 ,表示结点 间一条权值为 的边。
接下来 行,每行依次给出两个整数 ,分别表示必须经过的结点和选取的路径条数。
输出格式
输出 行,每行一个整数,表示对应询问的最大边权和。
样例
6 3
1 2 2
2 3 2
3 4 2
4 6 1
3 5 10
3 1
4 1
2 2
14
13
17
数据范围
,,。所有边权之和不超过 。
[NOI 2015 练习题原赛简要题解](file://solution.pdf)。询问次序和边权条件按本站原样例、原赛题解及现有评测校订。