結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2020-04-28 01:31:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 776 ms / 2,000 ms |
コード長 | 2,156 bytes |
コンパイル時間 | 210 ms |
コンパイル使用メモリ | 82,696 KB |
実行使用メモリ | 164,300 KB |
最終ジャッジ日時 | 2024-11-22 19:17:21 |
合計ジャッジ時間 | 7,397 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
mod = 1000000007eps = 10**-9def main():import sysinput = sys.stdin.readlineclass Bit:def __init__(self, n):self.size = nself.tree = [0] * (n + 1)def sum(self, i):s = 0while i > 0:s += self.tree[i]i -= i & -ireturn sdef add(self, i, x):while i <= self.size:self.tree[i] += xi += i & -idef lower_bound(self, w):if w <= 0:return 0x = 0k = 1 << (self.size.bit_length() - 1)while k:if x + k <= self.size and self.tree[x + k] < w:w -= self.tree[x + k]x += kk >>= 1return x + 1# adj[0] must be empty listdef EulerTour(adj, root):st = [root]ret = []seen = [0] * len(adj)par = [0] * len(adj)depth = [0] * len(adj)while st:v = st.pop()if seen[v]:ret.append(v)continueret.append(v)seen[v] = 1if par[v] != 0:st.append(par[v])for u in adj[v]:if seen[u] == 0:st.append(u)par[u] = vdepth[u] = depth[v] + 1return ret, depthN = int(input())A = list(map(int, input().split()))adj = [[] for _ in range(N+1)]for i in range(N-1):v = i+2p = A[i] + 1adj[v].append(p)adj[p].append(v)et, depth = EulerTour(adj,1)bit = Bit(len(et))cnt = [0] * (N+1)v_idx = [[] for _ in range(N+1)]for i, v in enumerate(et):cnt[v] += 1v_idx[v].append(i+1)for i, v in enumerate(et):bit.add(i+1, 1 / cnt[v])ans = 0for v in range(1, N+1):ans += bit.sum(v_idx[v][-1]) - bit.sum(v_idx[v][0]-1) - 1for i in v_idx[v]:bit.add(i, -1 / cnt[v])print(round(ans))if __name__ == '__main__':main()