问几个问题

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

_fairytale_ @ 2023-10-17 22:39:27

1.关于本题推的式子:

dep[s]-2dep[lca]=w[j]-dep[j]

我在每条路径输入后是这么写的；

modify(rt[t],-n,n,(dep[s]-dep[lca]-dep[lca]),1);
        modify(rt[fa[lca]],-n,n,(dep[s]-dep[lca]-dep[lca]),-1);

然后在线段树合并后这么查询：

if(w[u])ans[u]+=query(rt[u],-n,n,w[u]+dep[u]);
    ans[u]+=query(rt[u],-n,n,(w[u]-dep[u]));

而当我把以上两段改成这样就对了：

modify(rt[t],-n,n,-(dep[s]-dep[lca]-dep[lca]),1);
        modify(rt[fa[lca]],-n,n,-(dep[s]-dep[lca]-dep[lca]),-1);
if(w[u])ans[u]+=query(rt[u],-n,n,w[u]+dep[u]);
    ans[u]+=query(rt[u],-n,n,-(w[u]-dep[u]));

这是为什么呢？

然后还有

if(w[u])ans[u]+=query(rt[u],-n,n,w[u]+dep[u]);

一句中为什么要判 w[u]!=0 呢

我好像不是很懂，望大佬讲讲。

by __Aaaaaaaa @ 2023-10-18 12:08:38

我怀疑你跟我做的不是一道题

by _fairytale_ @ 2023-10-18 15:38:09

@Aaron_wch 我用的线段树合并/kel

可能大佬做法跟我不一样 QWQ

by bloodstalk @ 2023-10-18 18:37:32

我怀疑我不会这道题

by OcTar @ 2023-10-19 10:30:13

您的狮子太强了

by _fairytale_ @ 2023-10-19 15:30:54

知道了，警示后人，s 和 t 的贡献要开两棵线段树，题解的写法不知道为什么能过，疑似是平移值域导致的...？总之最好别照着题解写，线段树合并的话最好开两棵。

by pedestrian_ @ 2023-11-01 08:24:58

@fairytale 这个式子要处理一下，因为直接维护可能会算到另一边的贡献，把第一个等式两边取反后得到：

2*dep[lca]-dep[s]=dep[u]-w[u]

dep[s]=dep[u]+w[i]

由于当前点 u 和起点 s 的 dep 之和大于等于 dep[lca]*2 ，dep[u] 又小于等于 dep[s] 所以两个式子的贡献不会算重，当 w[i]=0 时两个式子右边的值相同，所以只用算一次就可以得到两个式子的贡献。

by Rosick @ 2023-11-09 17:28:21

@pedestrian_ dep[u] 为什么小于等于 dep[s]

by Rosick @ 2023-11-09 18:58:00

@pedestrian_ 懂了，因为dep[s]如果小于dep[u]，它就不在u的子树上，也就不会作用于它，orz