2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:dsu_on_tree [CVBB ACM Team]

Warning: session_start(): open(/tmp/sess_f129f6bc331c67da6856effb4fe618a4, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:dsu_on_tree [CVBB ACM Team]

2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:dsu_on_tree

MAIN

主要依据轻重链思想，暴力统计轻儿子对当前节点答案贡献，先递归解决轻儿子并消除影响，再递归重儿子并保留影响用于此节点统计答案。

全局时间复杂度 $O(nlogn)$

2020-2021/teams/looking_up_at_the_starry_sky/shenzhonghai/dsu_on_tree.1600847951.txt.gz · 最后更改: 2020/09/23 15:59 由 x342333349