给定一个树,树上的边都具有权值。
树中一条路径的异或长度被定义为路径上所有边的权值的异或和:!!树是啥?权值是啥?异或是啥???(逃
为异或符号。
给定上述的具有 个节点的树,你能找到异或长度最大的路径吗?别想,除了zzh和yys这两位以及yzy这位以外谁都不能(我这个蒻蘜早已瑟瑟发抖)
真的不要看这个真的没用的提示
先随便挑个根节点(反正是树)
用表示节点的简单路径上所有边权的异或值,表示的最近公共祖先,表示根节点,那么有
^
^ ^ ^ ^ ^
^ ^ ^
^ ^ ^
^
知道这个结论后,求所有节点与节点的路径权值的异或值
最后直接取就可以啦QAQ
myd
实在不会就去瞅我(myd)博客的标程 ♪───O(≧∇≦)O────♪
不许抄袭!!!😈😈😈