hdu 5416 CRB and Tree ( 2015 多校 #10 )

http://acm.hdu.edu.cn/showproblem.php?pid=5416
题意:给出一棵树(n<=1E5),定义二元函数函数f(u,v) (u可以等于v)表示节点u到节点v经过的路径的权值的异或和。给出q组查询(q<=10),每组一个s,问有多少对无序点对(u,v)满足f(u,v)=s.
思路:类似codeforces #340 div 2 E XOR and Favorite Number
先dfs,处理出从根节点都任意节点的异或前缀和。然后对于每个询问o(n)扫一遍,统计sum[i]^s出现多少次。 总的时间复杂度为O(T*q*n);

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz