51 lines
No EOL
1.2 KiB
Python
51 lines
No EOL
1.2 KiB
Python
import sys
|
|
|
|
data = sys.stdin.read().split()
|
|
n, m = int(data[0]), int(data[1])
|
|
parents = [0] * n
|
|
idx = 2
|
|
for i in range(1, n):
|
|
parents[i] = int(data[idx])
|
|
idx += 1
|
|
a1, a2 = int(data[idx]), int(data[idx+1])
|
|
x, y, z = int(data[idx+2]), int(data[idx+3]), int(data[idx+4])
|
|
adj = [[] for _ in range(n)]
|
|
for i in range(1, n):
|
|
adj[parents[i]].append(i)
|
|
depth = [0] * n
|
|
q = [0]
|
|
for u in q:
|
|
for v in adj[u]:
|
|
depth[v] = depth[u] + 1
|
|
q.append(v)
|
|
up = [[0] * 18 for _ in range(n)]
|
|
for i in range(1, n):
|
|
up[i][0] = parents[i]
|
|
for k in range(1, 18):
|
|
for i in range(n):
|
|
up[i][k] = up[up[i][k-1]][k-1]
|
|
a = [0] * (2 * m + 1)
|
|
a[1], a[2] = a1, a2
|
|
for i in range(3, 2 * m + 1):
|
|
a[i] = (x * a[i-2] + y * a[i-1] + z) % n
|
|
ans = 0
|
|
v = 0
|
|
for i in range(1, m + 1):
|
|
u = (a[2*i-1] + v) % n
|
|
vq = a[2*i]
|
|
if depth[u] < depth[vq]:
|
|
u, vq = vq, u
|
|
diff = depth[u] - depth[vq]
|
|
for k in range(18):
|
|
if (diff >> k) & 1:
|
|
u = up[u][k]
|
|
if u == vq:
|
|
v = u
|
|
else:
|
|
for k in range(17, -1, -1):
|
|
if up[u][k] != up[vq][k]:
|
|
u = up[u][k]
|
|
vq = up[vq][k]
|
|
v = up[u][0]
|
|
ans += v
|
|
print(ans) |