codeforces-930A-Peculiar apple-tree[流量]

发表于 更新于 分类于 阅读次数：

描述

又是一个讲故事的题…

本质是有一棵(颠倒的)树, 除了根节点, 每个节点有(唯一一个)子节点. 初始时刻, 每个节点都有一颗苹果, 然后每过一个时间单位, 所有苹果都会坠落到它的子节点. 如果同时有n个苹果坠落到同一个节点, 那么这些苹果会两两抵消(消失). 也就是n为偶数, 结果是0,否则为1. 问最终(从根节点)可以收集到多少个苹果.

思路

所有苹果同步下降, 对于每个节点, 我们只关心它的所有父节点的贡献. 这样可以bfs层序遍历一下, 统计每层的苹果数量, 奇数对应1, 偶数对应0.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import collections
def do():
    n = int(input())
    nums = [0] + [int(c)-1 for c in input().split(" ")]
    g = collections.defaultdict(list)
    for i, j in enumerate(nums):
        if i != j:
            g[j].append(i)
    cur = [0]
    res = 0
    while cur:
        res += len(cur) % 2
        next = []
        for c in cur:
            for nei in g[c]:
                next.append(nei)
        cur = next
    return res

print(do())