求助，为什么这道题一定要开两个桶来统计？？

P1600 [NOIP2016 提高组] 天天爱跑步

10MN47 @ 2019-10-29 19:37:54

这道题目我开了两个桶就A了，但是只开一个桶就只有30分。

by 10MN47 @ 2019-10-29 19:40:28

我在预处理时，已经分别处理了路径只在lca左边，只在lca右边，跨过lca的情况。

by ZhuMingYang @ 2019-10-29 19:42:16

@10MN47 这你都没弄懂是怎么过的。。

by ZhuMingYang @ 2019-10-29 19:42:45

因为向上跑和向下跑是不同的判断条件

by HRLYB @ 2019-10-29 21:02:35

同机房出来凑个热闹

by 10MN47 @ 2019-10-29 21:08:26

@ZhuMingYang

大佬可以讲的详细一点吗，我在一开始差分的时候，已经处理了向上跑和向下跑的情况了。

by _Xolotl_ @ 2019-10-29 21:09:00

热闹加一

by ZhuMingYang @ 2019-10-29 21:24:01

@10MN47 emm...

因为向上跑是

dep_i+w_i=dep_s

向下跑是

dep_i-w_i=2\times dep_{lca(s,t)}-dep_s

by ZhuMingYang @ 2019-10-29 21:25:46

分别用两个线段树处理

向上路径和向下路径即可

by 10MN47 @ 2019-10-29 21:33:08

@ZhuMingYang

大佬，我可以发我的代码给你看看吗？

by ZhuMingYang @ 2019-10-29 21:34:05

@10MN47 发呀

| 下一页