#P4363. Path

    ID: 3566 传统题 1000ms 512MiB 尝试: 7 已通过: 5 难度: 9 上传者: 标签>CF2800省选/NOI-边际收益贪心换根 DP可持久化线段树路径复制离散化线段树上二分

Path

题目描述

给定一棵 nn 个结点的无根树,每条边有正整数权值。

每次询问给出结点 xx 和正整数 kk。选择 kk 条简单路径,要求至少一条路径经过 xx,并使这些路径覆盖的边的权值之和最大。若多条路径经过同一条边,只计一次该边权值。

输入格式

第一行两个整数 n,mn,m,分别表示结点数和询问数。

接下来 n−1n-1 行,每行三个整数 u,v,wu,v,w,表示结点 u,vu,v 间一条权值为 ww 的边。

接下来 mm 行,每行依次给出两个整数 x,kx,k,分别表示必须经过的结点和选取的路径条数。

输出格式

输出 mm 行,每行一个整数,表示对应询问的最大边权和。

样例

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

数据范围

1≤n,m≤1051\le n,m\le10^5,1≤x≤n1\le x\le n,k≥1k\ge1。所有边权之和不超过 231−12^{31}-1。

[NOI 2015 练习题原赛简要题解](file://solution.pdf)。询问次序和边权条件按本站原样例、原赛题解及现有评测校订。