Loading...

[省选联考 2020 A 卷] 树

check评论:0 条 remove_red_eye浏览量:87 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2020-06-24

题意:给定一棵 $n$ 个点的树,第 $i$ 个点有权值 $v_i$,$val_x=v_x \oplus (d(x,y)+v_y) \oplus ... (y\in son_x)$,求 $\sum\limits_{i=1}^n val(i)$,其中 $d(x,y)$ 代表 $x\rightarrow y$ 的距离。

考虑 $01trie$ 合并,每次合并子树答案,然后将全局 $+1$,再插入自己即可,$+1$ 的时候交换左右儿子,一直往交换后的左儿子走即可。

时间复杂度 $O(n \log n)$

chevron_left 哇 没了

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名