#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号点外,每个点的编号都比其父节点的编号大。

提示

请注意答案可能的取值范围。