Advertisement
Guest User

div1-medium

a guest
Apr 18th, 2017
302
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.97 KB | None | 0 0
  1. from math import factorial as fact
  2.  
  3. def binom(n, k):
  4.     return fact(n) // fact(k) // fact(n - k)
  5.  
  6.  
  7. def dfs(v, sz, a, b, c, d, g, w):
  8.     sz[v] = 1
  9.     a[v][1] = 1
  10.     b[v][1] = w[v]
  11.     d[v][1] = w[v] * w[v]
  12.     c[v][1] = 0
  13.  
  14.     for to in g[v]:
  15.         dfs(to, sz, a, b, c, d, g, w)
  16.         for k in range(sz[v], 0, -1):
  17.             for i in range(sz[to], 0, -1):
  18.                 a[v][k + i] += a[v][k] * a[to][i]
  19.  
  20.                 b[v][k + i] += b[v][k] * a[to][i] + b[to][i] * a[v][k]
  21.                 d[v][k + i] += d[v][k] * a[to][i] + d[to][i] * a[v][k]
  22.  
  23.                 c[v][k + i] += c[v][k] * a[to][i] + c[to][i] * a[v][k]
  24.                 c[v][k + i] += b[v][k] * b[to][i]
  25.                
  26.         sz[v] += sz[to]
  27.    
  28.  
  29. def calc(n):
  30.     c1 = [0] * (n + 1)
  31.     c2 = [0] * (n + 1)
  32.     for m in range(1, n + 1):
  33.         c1[m] = m ** (-1) - m ** (-2)
  34.  
  35.     for m in range(1, n + 1):
  36.         c2[m] = -2  * (m ** (-2))
  37.  
  38.     return c1, c2
  39.  
  40.  
  41. class AverageVarianceSubtree:
  42.     def average(self, p, w):
  43.         n = len(w)
  44.         g = [[] for _ in range(n)]
  45.         for v in range(1, n):
  46.             g[p[v - 1]].append(v)
  47.  
  48.         sz = [0] * n
  49.         a = [[0] * (n + 1) for _ in range(n)]
  50.         b = [[0] * (n + 1) for _ in range(n)]
  51.         c = [[0] * (n + 1) for _ in range(n)]
  52.         d = [[0] * (n + 1) for _ in range(n)]
  53.  
  54.         root = 0
  55.         dfs(root, sz, a, b, c, d, g, w)
  56.         c1, c2 = calc(n)
  57.  
  58.         ans = 0
  59.         tot = 0
  60.         for v in range(n):
  61.             for m in range(1, sz[v] + 1):
  62.                 tot += a[v][m]
  63.                 ans += c1[m] * d[v][m] + c2[m] * c[v][m]
  64.                 print(v, m)
  65.                 print(d[v][m], c[v][m])
  66.                 print()
  67.                
  68.  
  69.         print('tot = ', tot)
  70.  
  71.         return ans / tot
  72.  
  73.  
  74.  
  75. if __name__ == '__main__':
  76.     solver = AverageVarianceSubtree()
  77.     p = list(map(int, input().split()))
  78.     w = list(map(int, input().split()))
  79.     print(solver.average(p, w))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement