#PQJ1857x9643. QOJ 1857_9643

    ID: 2736 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测树形DP线段树

QOJ 1857_9643

标题: 串联 - Problem - QOJ.ac

#9643. 串联

Statistics

The problem was used in the following contests:

题目描述

给一棵 n 个点的树,每个点有两个权值 ai,bi。对于树上的一条简单路径,若这条路径上 b 之和乘上 a 的最小值大于等于一个常数 V,那么这条路径被称作一条好的路径。

即:对于一条简单路径,设 p1,p2,…,pk 为路径上的点。这条简单路径是好的,当且仅当 mini=1kapi×∑i=1kbpi≥V。

求所有好的路径中,∑b 的最小值。

输入格式

第一行两个整数 n,V。

接下来 n 行每行两个整数 ai,bi。

接下来 n−1 行每行两个整数 xi,yi,表示一条树边。

输出格式

一行一个整数表示答案。

样例

样例 0 输入

10 100
4 8
7 6
4 6
5 5
4 4
7 4
5 4
8 8
5 5
6 4
1 8
1 2
2 3
2 6
10 9
4 1
4 9
5 7
5 4

样例 0 输出

25

样例 1 输入/输出

见附加文件 series1.in/series1.out,该样例满足子任务一的限制。

样例 2 输入/输出

见附加文件 series2.in/series2.out,该样例满足子任务二的限制。

样例 3 输入/输出

见附加文件 series3.in/series3.out,该样例满足子任务三的限制。

样例 4 输入/输出

见附加文件 series4.in/series4.out,该样例满足子任务四的限制。

样例 5 输入/输出

见附加文件 series5.in/series5.out,该样例满足子任务五的限制。

样例 6 输入/输出

见附加文件 series6.in/series6.out,该样例满足子任务六的限制。

子任务

对于所有测试点均满足 1≤V≤1018,1≤ai,bi≤109。数据保证有解。

子任务编号 n≤ 特殊性质 分值 1 2×103 无 15 2 104 15 3 2×105 存在一个点度数为 n−1 15 4 第 i 条边连接 i 和 i+1 15 5 5×104 无 20 6 2×105 20