CF1338 B. Edge Weight Assignment
CF1338 B. Edge Weight Assignment 题意 一棵n个结点的树,求最小和最大需要多少个不同的路径来构造树的路径权值,使得任意两片叶子的路径异或和为0。 思路 首先这是一棵无根树,以其任意一个叶子结点为根。(避免讨论) 首先考虑最小,最小要么为1要么为3。 为1的情况是任意结点到根节点的距离为偶数。 为3的情况是只要有一个结点到根结点的距离为奇数。 这里仅判断奇偶有两种写法,1是记录深度,2是利用异或。 1^1=0 0^1=1 接着考虑最大,我们发现当一个父节点直接与>1个叶子结点相连,则由于那些叶子结点到父节点的距离为1,所以他们的边权值一定相等,故这些边视为一样的
用户评论