HDU 5692 Snacks

  • 2018-09-26
  • 16
  • 0

Description:

百度科技园内有n个零食机,零食机之间通过n−1条路相互连通。每个零食机都有一个值v,表示为小度熊提供零食的价值。

由于零食被频繁的消耗和补充,零食机的价值v会时常发生变化。小度熊只能从编号为0的零食机出发,并且每个零食机至多经过一次。另外,小度熊会对某个零食机的零食有所偏爱,要求路线上必须有那个零食机。

为小度熊规划一个路线,使得路线上的价值总和最大。

Input:

输入数据第一行是一个整数T(T≤10),表示有T组测试数据。

对于每组数据,包含两个整数n,m(1≤n,m≤100000),表示有n个零食机,m次操作。

接下来n−1行,每行两个整数x和y(0≤x,y<n),表示编号为x的零食机与编号为y的零食机相连。

接下来一行由n个数组成,表示从编号为0到编号为n−1的零食机的初始价值v(|v|<100000)。

接下来m行,有两种操作:0 x y,表示编号为x的零食机的价值变为y;1 x,表示询问从编号为0的零食机出发,必须经过编号为x零食机的路线中,价值总和的最大值。

本题可能栈溢出,辛苦同学们提交语言选择c++,并在代码的第一行加上:

Output

对于每组数据,首先输出一行”Case #?:”,在问号处应填入当前数据的组数,组数从1开始计算。

对于每次询问,输出从编号为0的零食机出发,必须经过编号为x零食机的路线中,价值总和的最大值。

Sample Input:

1
6 5
0 1
1 2
0 3
3 4
5 3
7 -5 100 20 -5 -7
1 1
1 3
0 2 -1
1 1
1 5

Sample Output:

Case #1:
102
27
2
20

题目链接

通过dfs序建立线段树,线段树维护树上各节点到0节点的距离,更新时通过节点dfs序两个编号进行区间更新(自己及子节点更新)。

AC代码:

评论

还没有任何评论,你来说两句吧