[原创]Codeforces 766E Mahmoud and a xor trip [二进制,]【数学+思维】
[原创]Codeforces 766E Mahmoud and a xor trip [二进制,]【数学+思维】
2017-02-09 00:22:39 Tabris_ 阅读数:726
博客爬取于2020-06-14 22:41:45
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54935260
题目连接:http://codeforces.com/contest/766/problem/E
------------------------------------------------------------------------------.
------------------------------------------------------------------------------.
题目大意:
就是在一个生成树上求任意两点的距离的和,距离定义为两点间路上所有点权值的异或和,
解题思路:
想法就是将结果的异或和拆分成每一位的,就是对于二进制数上对于第i位,有多少个距离为1的路径,然后在总结果上即可,这样最多按二进制位数个的搜索一遍树就行了.
cnt[][0]是以u为根0的个数,cnt[][1]同理.
听闻这题还有树分治和树dp的做法,有兴趣可以百度一发.
附本题代码
------------------------------------------------------------------------------.
1 | int a[N],b[N],cnt[N][2]; |
对于对树、图进行dfs的要好好练练 总是搜不明白.
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 tabris的博客!
评论