HDU 5956 树上进行斜率优化DP + 记录操作并撤销

http://acm.hdu.edu.cn/showproblem.php?pid=5956

The Elder

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)


Problem Description

Once upon a time, in the mystical continent, there is a frog kingdom, ruled by the oldest frog, the Elder. The kingdom consists of N cities, numbered from east to west. The 1-th city, which is located to the east of others, is the capital. Each city, except the capital, links none or several cities to the west, and exactly one city to the east.
There are some significant news happening in some cities every day. The Elder wants to know them as soon as possible. So, that is the job of journalist frogs, who run faster than any other frog. Once some tremendous news happen in a city, the journalist in that city would take the message and run to the capital. Once it reach another city, it can either continue running, or stop at that city and let another journalist to transport. The journalist frogs are too young and simple to run a long distance efficiently. As a result, it takes $L^2$ time for them to run through a path of length L. In addition, passing message requires P time for checking the message carefully, because any mistake in the message would make the Elder become extremely angry.
Now you are excited to receive the task to calculate the maximum time of sending a message from one of these cities to the capital.

Input

The first line of input contains an integer t, the number of test cases. t test cases follow. For each test case, in the first line there are two integers N (N ≤ 100000) and P (P ≤ 1000000). In the next N-1 lines, the i-th line describes the i-th road, a line with three integers u,v,w denotes an edge between the u-th city and v-th city with length w(w ≤ 100).

Output

For each case, output the maximum time.

Sample Input

3
6 10
1 2 4
2 3 5
1 4 3
4 5 3
5 6 3
6 30
1 2 4
2 3 5
1 4 3
4 5 3
5 6 3
6 50
1 2 4
2 3 5
1 4 3
4 5 3
5 6 3

Sample Output

51
75
81

Hint

In the second case, the best transportation time is: • The 2-th city: 16 = 4^2 • The 3-th city: 72 = 4^2 + 30 + 5^2 • The 4-th city: 9 = 3^2 • The 5-th city: 36 = (3 + 3)^2 • The 6-th city: 75 = (3 + 3)^2 +30 + 3^2 Consequently, the news in the 6-th city requires most time to reach the capital.

Source

题目翻译

从前,在神秘的大陆,有一个青蛙王国,由最年长的青蛙——长者统治着。这个王国由N座城市组成,从东到西编号。第一座城市是首都,座落在最东边。每一个城市,连接者几个或者没有连接几个西边的城市,并且只连接了一个东边的城市。
每天,都有一些大新闻发生在一些城市。长者想尽快地知道。所以,青蛙新闻工作者的工作就是,跑得比其他青蛙都快。当有巨大新闻发生在某座城市的时候,这座城市的新闻工作者将会携带信息,跑向首都。当到达另一个城市的时候,他可以继续跑,也可停下来让其他的新闻工作者传输信息。这些新闻工作者由于太年轻并且简单,不能有效的跑很长的距离。结果,他们需要 $L^2$的时间来跑一条长度为L的路径。除此之外,传达信息需要P的时间,是为了检查传达信息是否有误,因为信息的误差会使长者极度的生气。
现在你高兴的收到一个任务:计算从所有城市发送信息到首都的所需的最长的时间。
 

思路

可以将图看成一个由1点为根的树,每个点到根结点为路径是唯一的。设dp[u]为u点传输信息到根节点的所需时间。a[u]为u点到根节点的距离。很明显,dp[u] = min{dp[k]+$(a[u]-a[k])^2$+P | k是u的祖先)。用斜率优化优化DP转移即可。但是不同的点路径不同,所以这里还需要记录在这个点对于斜率优化的队列操作了什么,回溯离开这个点的时候,需要撤销这些操作,操作每个点有一个栈记录即可。对于从根节点转移吃出来,可以考虑单独转移,也可设置dp[1]=-P