Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from math import factorial as fact
- def binom(n, k):
- return fact(n) // fact(k) // fact(n - k)
- def dfs(v, sz, a, b, c, d, g, w):
- sz[v] = 1
- a[v][1] = 1
- b[v][1] = w[v]
- d[v][1] = w[v] * w[v]
- c[v][1] = 0
- for to in g[v]:
- dfs(to, sz, a, b, c, d, g, w)
- for k in range(sz[v], 0, -1):
- for i in range(sz[to], 0, -1):
- a[v][k + i] += a[v][k] * a[to][i]
- b[v][k + i] += b[v][k] * a[to][i] + b[to][i] * a[v][k]
- d[v][k + i] += d[v][k] * a[to][i] + d[to][i] * a[v][k]
- c[v][k + i] += c[v][k] * a[to][i] + c[to][i] * a[v][k]
- c[v][k + i] += b[v][k] * b[to][i]
- sz[v] += sz[to]
- def calc(n):
- c1 = [0] * (n + 1)
- c2 = [0] * (n + 1)
- for m in range(1, n + 1):
- c1[m] = m ** (-1) - m ** (-2)
- for m in range(1, n + 1):
- c2[m] = -2 * (m ** (-2))
- return c1, c2
- class AverageVarianceSubtree:
- def average(self, p, w):
- n = len(w)
- g = [[] for _ in range(n)]
- for v in range(1, n):
- g[p[v - 1]].append(v)
- sz = [0] * n
- a = [[0] * (n + 1) for _ in range(n)]
- b = [[0] * (n + 1) for _ in range(n)]
- c = [[0] * (n + 1) for _ in range(n)]
- d = [[0] * (n + 1) for _ in range(n)]
- root = 0
- dfs(root, sz, a, b, c, d, g, w)
- c1, c2 = calc(n)
- ans = 0
- tot = 0
- for v in range(n):
- for m in range(1, sz[v] + 1):
- tot += a[v][m]
- ans += c1[m] * d[v][m] + c2[m] * c[v][m]
- print(v, m)
- print(d[v][m], c[v][m])
- print()
- print('tot = ', tot)
- return ans / tot
- if __name__ == '__main__':
- solver = AverageVarianceSubtree()
- p = list(map(int, input().split()))
- w = list(map(int, input().split()))
- print(solver.average(p, w))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement