有道面试

Case Time Limit: 1000ms

Memory Limit: 65536KB

 

Description

 

有N个村庄，村庄之间有N-1条路，每条路都有一个长度。这些村庄和路形成了一个树形结构。现在要求从某个村庄出发，通过这些路访问所有的村庄，起点村庄当做已经被访问过。现在有若干个村庄可以作为起点村庄。问访问全部的村庄所要走的路程之和最小是多少。

Input

输入的第一行为一个正整数N(1≤N≤100000)。接下来的N-1行每行三个数X,Y,Z(1<=X,Y<=N, 1<=Z<=10000)表示X号村庄和Y号村庄间有一条长度为Z的路。接下来的一行包含N个数每个数不是0就是1，若第i个数是1表示可以选择该点为起始村庄否则不可以。

Output

输出一个非负整数表示访问全部的村庄所要走的最小路程之和。若无法访问全部村庄输出-1。

Sample Input

51 2 11 3 13 4 33 5 41 1 1 0 0

Sample Output

12

Source

 

 

感觉是比较经典的树形dp的变形吧。

路径要两遍dfs。第一次 处理子树的路径，第二次传递路径信息到子树上，要注意的是第二次传递时候要保存最大的一个和第二大的一个(这样传递给最大的子树时候用第二大的路径信息)。

代码就不上传了。