首页 > Tree Xor
开通博客写题解
头像 Kur1su
发表于 2021-07-28 17:09:01
Description 给出一棵树，权值未知，但是给出每条边两个端点权值的异或值，求原来的权值。 Solution 假设权值 ，那么从它开始进行一遍 赋值可以得到所有点当前的权值 。当然 不一定等于 ，假设 ，那么真实的 。 现在给出每个 的范围满足 ，即 ，设 ，等式两边异或上 得到 ， 展开全文
去ta的博客 赞 (16) 回复(1) 收起
头像 河南老乡唐可可
发表于 2021-08-09 10:49:53
E题蒟蒻听直播听的不是特别懂，有很多疑惑，于是看了看dalao们的代码和解释，于是就有了这篇题解，侧重于本鶸不太懂得地方，可能对大家有帮助。 题目大意 给定一棵有n个节点的树，每个节点的权值​​​未知，满足​​​，其中​​​为给定数值。每条边的权值为已知，其值为它连接的两个边的权值的异或值。求出满足 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-08-20 10:17:20
题目大意 你有一个一颗树节点数，树上的边有一个边权，点有一个点权，你要保证有直接父子关系的点之间，并且树上每个点他的点权选取范围为，现在请问你能构造出多少颗不同的树，有任何一个不同就认为是一颗不同的树。 Solution 考点：线段树区间性质 首先树上边权关系给你了，所以当我们顶下后整棵树后续的都会 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”