#P2021125. 极差路径
极差路径
极差路径
题目描述
题目背景
众所周知,西西艾弗岛是一个旅游胜地,但是由于兴建机场,西西艾弗岛最近的财务状况有点紧张。
题目描述
为了从游客手中获取更多的经济利润,岛上仅有的三个小学生小 C、小 S 和小 P建立了n个景点,编号依次从1到n。编号为i的景点是第i个被修建的。由于越到后期经费越是不足,所以编号更大的景点通常更令人不满意——方便起见,假定编号为i的景点的令人不满意程度是i。
有些景点之间修有双向可通行的道路,但是出于减少经费的考虑,他们只修了能使得所有景点连通的最少数量的道路,从而这些景点和其间的道路形成一棵树的结构。
对于每个游客而言,由于只修了n−1条道路,所以他只能沿着树上的边参观,并且由于他不可能重复参观一个景点,所以他的游览路径一定是树上的一条简单路径。
现在西西艾弗岛希望制定一些推荐游览路径,但并非所有树上的路径都是合意的,因为这条路径上的景点令人不满意程度的极差可能过大,使游客产生这些景点质量不稳定的错觉。由于最开始的景点和最后的景点令人印象比较深刻,所以游客通常会把游览路径上的景点和这两个景点作比较。因此,最令人不满意的景点不能比这两个景点差太多,最优秀的景点也不能比这两个景点优秀太多。
具体来说,一条从x到y的游览路径(记作(x,y))是推荐的,当且仅当下式成立: minx,y−k1≤minP(x,y)≤maxP(x,y)≤maxx,y+k2 其中P(x,y)表示一条从x出发到达y的简单路径上的点的令人不满意程度的数值的集合(包括x和y,也就是x到y的简单路径上的点的编号的集合),minS和maxS分别表示集合S中的最小和最大值,k1,k2是西西艾弗岛经过数次尝试后选取的两个给定的参数,保证k1,k2≥0。
特别的,容易验证x=y时(x,y)总是推荐的。
现在西西艾弗岛想知道,一共有多少树上的简单路径作为游览路径是被推荐的?这里我们认为(x,y)和(y,x)是同一条路径。
输入格式
从标准输入读入数据。
第一行输入三个非负整数n,k1,k2。
接下来n−1行,每行两个正整数x,y表示树上的一条边。
输出格式
输出到标准输出。
输出一行一个非负整数表示答案。
数据范围
(原站未提供,导入后需人工补齐)
样例
5 0 1
5 4
4 2
4 1
2 3
12
提示
样例1解释
容易验证(1,1),(1,4),(1,5),(1,3),(2,2),(2,4),(2,5),(2,3),(3,3),(4,4),(4,5),(5,5)都是推荐的游览路径,因此答案是12。
子任务
测试点n≤k1k2树的形态堆性质
15000≤n≤nA3无
25000≤n≤nA3无
35000≤n≤nA3无
45×10^5=0=0A1有
55×10^5=0=0A1无
65×10^5≤n=0A1有
75×10^5≤n=0A1无
85×10^5≤n≤nA1有
95×10^5≤n≤nA1无
105×10^5=0=0A2无
115×10^5≤n=0A2无
125×10^5≤n≤nA2无
135×10^5=0=0A3有
145×10^5=0=0A3无
155×10^5=0=0A3无
165×10^5=0=0A3无
175×10^5≤n=0A3有
185×10^5≤n=0A3无
195×10^5≤n=0A3无
205×10^5≤n=0A3无
215×10^5≤n≤nA3有
225×10^5≤n≤nA3有
235×10^5≤n≤nA3无
245×10^5≤n≤nA3无
255×10^5≤n≤nA3无
对于100的数据,1≤n≤5×10^5,0≤k1,k2,≤n,保证输入的n−1条边一定构成一棵树。
树的形态:
A1:树是一条链 ;
A2:存在一个度数为n−1的点;
A3:树的形态无特殊性质。
堆性质:若取编号为1的点为根,则除1号点外,每个点的编号都比其父节点的编号大。
提示
请注意答案可能的取值范围。