Related
In following contests:
题目保证目标群落包含初始群落的所有菌株,且相同编号的菌株在两种群落中的父子关系完全相同。故前 n 个菌株无需考虑是否相同的问题。
从目标群落的第 n+1 个菌株开始,均为新增的菌株。这些新增菌株需要满足:其父亲编号都各不相同,且父亲编号都必须小于等于 n,因为大于 n 的编号均为新增的菌株,根据题目要求不能作为其他菌株的父亲。
为了方便判断是否有两个新增菌株的父亲相同,将所有新增菌株按其父亲编号排序,如果两个菌株的父亲编号相同,则这两个菌株在排序后必然相邻。
科学家在实验室培养一种树状分裂的细菌群落。每一株细菌都有一个编号,初始群落形成一棵以 1 号菌株为根的树,菌株之间的父子关系构成树的边。每年,每株细菌最多进行一次分裂,产生一个新的子菌株,直接连接在该菌株上。新产生的菌株不能继续分裂(即新菌株只能是叶子),也不能作为其他新菌株的父节点。换句话说,目标群落必须由初始群落经过以下操作得到:选择初始群落中的若干菌株,为每个被选中的菌株至多添加一个新的直接子菌株,且所有新菌株的父亲必须来自初始群落。
给定初始群落与一个目标群落的结构,你需要判断目标群落是否有可能恰好经过一年的分裂得到。保证目标群落包含初始群落的所有菌株,且相同编号的菌株在两种群落中的父子关系完全相同。
约束条件:
In following contests:
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册