[SRM786] TwoDistance
题目描述
给定一棵有 N 个节点的无向树,节点编号为 0,1,…,N−1,节点 x 的值为 Vx。距离指两节点之间最短路的边数。
令 Sx 为与节点 x 的距离恰好为 2 的所有节点组成的集合。如果 ∣Sx∣<2,节点 x 的代价为 0;否则其代价为
a,b∈Sx, a=bmin∣Va−Vb∣.
求所有节点代价之和。不同节点可以有相同的值。
树与点值的生成
输入给出 N,D,seed,以及父节点数组和点值数组的前缀 edge、val。所有数组均从下标 0 开始。
- 令 A0=seed;对于 1≤i<2N,计算 Ai=(1103515245Ai−1+12345)mod2147483648。
- 对于 i<∣val∣,令 Vi=vali;其余 i<N 令 Vi=Ai。
- 对于 i<∣edge∣,令 Ei=edgei;其余 i<N 令 Ei=AN+imodmin(i,D)。
- 对于 1≤i<N,连接无向边 (i,Ei)。E0=−1,不为它建立边。
生成器中的乘法使用 64 位整数,先计算完整乘积再取模。
输入格式
第一行三个整数 N,D,seed。
接下来一个整数 e,随后 e 个整数表示 edge。再输入一个整数 v,随后 v 个整数表示 val。当 v=0 时没有点值前缀。上述整数可用任意空白分隔。
输出格式
一行一个整数,表示所有节点代价之和。结果需要用 64 位整数保存。
样例 1
3 1 1
1
-1
0
0
样例 2
10 9 340406567
1
-1
0
6115640787
数据范围
- 3≤N≤200000,1≤D≤N。
- 0≤seed≤2147483647。
- 1≤e≤min(N,100),edge0=−1;对于 1≤i<e,0≤edgei<i。
- 0≤v≤min(N,100),0≤vali≤2147483647。
本版采用普通输入输出,保留现行 Hydro 的 100 分整题评分。
来源:Topcoder SRM786 Division I Level Three,TwoDistance。原题面存档;原官方题号 pm/16112。