问几个问题

1.关于本题推的式子:

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

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

CPP

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);

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

CPP

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]));

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

CPP

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 呢

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

讨论操作

回复

相关推荐

问几个问题