#P17433. [SRM786] TwoDistance

[SRM786] TwoDistance

[SRM786] TwoDistance

题目描述

给定一棵有 NN 个节点的无向树,节点编号为 0,1,…,N−10,1,\ldots,N-1,节点 xx 的值为 VxV_x。距离指两节点之间最短路的边数。

令 SxS_x 为与节点 xx 的距离恰好为 2 的所有节点组成的集合。如果 ∣Sx∣<2|S_x|<2,节点 xx 的代价为 00;否则其代价为

min⁡a,b∈Sx, a≠b∣Va−Vb∣.\min_{a,b\in S_x,\ a\ne b}|V_a-V_b|.

求所有节点代价之和。不同节点可以有相同的值。

树与点值的生成

输入给出 N,D,seedN,D,seed,以及父节点数组和点值数组的前缀 edge、val。所有数组均从下标 00 开始。

  1. 令 A0=seedA_0=seed;对于 1≤i<2N1\le i<2N,计算 Ai=(1103515245Ai−1+12345) mod 2147483648A_i=(1103515245A_{i-1}+12345)\bmod 2147483648。
  2. 对于 i<∣val∣i<|val|,令 Vi=valiV_i=val_i;其余 i<Ni<N 令 Vi=AiV_i=A_i。
  3. 对于 i<∣edge∣i<|edge|,令 Ei=edgeiE_i=edge_i;其余 i<Ni<N 令 Ei=AN+i mod min⁡(i,D)E_i=A_{N+i}\bmod\min(i,D)。
  4. 对于 1≤i<N1\le i<N,连接无向边 (i,Ei)(i,E_i)。E0=−1E_0=-1,不为它建立边。

生成器中的乘法使用 64 位整数,先计算完整乘积再取模。

输入格式

第一行三个整数 N,D,seedN,D,seed。

接下来一个整数 ee,随后 ee 个整数表示 edge。再输入一个整数 vv,随后 vv 个整数表示 val。当 v=0v=0 时没有点值前缀。上述整数可用任意空白分隔。

输出格式

一行一个整数,表示所有节点代价之和。结果需要用 64 位整数保存。

样例 1

3 1 1
1
-1
0
0

样例 2

10 9 340406567
1
-1
0
6115640787

数据范围

  • 3≤N≤2000003\le N\le200000,1≤D≤N1\le D\le N。
  • 0≤seed≤21474836470\le seed\le2147483647。
  • 1≤e≤min⁡(N,100)1\le e\le\min(N,100),edge0=−1edge_0=-1;对于 1≤i<e1\le i<e,0≤edgei<i0\le edge_i<i。
  • 0≤v≤min⁡(N,100)0\le v\le\min(N,100),0≤vali≤21474836470\le val_i\le2147483647。

本版采用普通输入输出,保留现行 Hydro 的 100 分整题评分。

来源:Topcoder SRM786 Division I Level Three,TwoDistance。原题面存档;原官方题号 pm/16112。