P1600 [NOIP2016 提高组] 天天爱跑步 做题记录

首先不难发现一条路径可以分成深度递减的一段和深度递增的一段:

为了方便下文描述,我们称深度递减的那一段为”上升链“,深度递增的那一段为”下降链“

不难发现,对于路径 aba\to baabb 不是子孙关系,那么它的上升链为 alca(a,b)a\to \operatorname{lca}(a,b),下降链为 lca(a,b)b\operatorname{lca}(a,b) \to b,否则就只有上升链或下降链 aba\to b

那么考虑对上升链和下降链分别计算答案,最后加起来:(定义 depudep_u 为节点 uu 的深度)

  • 对于上升链:

    • 因为起点为 vv 的上升链能被 uu 观察到当且仅当 depvdepu=wudep_v-dep_u=w_u,移项得 depv=wu+depudep_v=w_u+dep_u
    • 所以可以在 dfs 的同时cnticnt_i 表示满足 depv=idep_v=i 且这条上升链经过 uu 的上升链的起点 vv 的个数
    • 那么上升链uu 的贡献即为 cntwu+depucnt_{w_u+dep_u}
  • 对于下降链:

    • stmevstme_v 表示这条下降链的开始时间,因为一个人要跑完上升链才会去跑下降链;

    • 因为起点为 vv 的下降链能被 uu 观察到当且仅当 depudepv=wustmevdep_u-dep_v=w_u-stme_v,移项得 stmevdepv=wudepustme_v-dep_v=w_u-dep_u

    • 所以可以在 dfs 的同时cnt2icnt2_i 表示满足 stmevdepv=istme_v-dep_v=i 且这条下降链经过 uu 的下降链的起点 vv 的个数

    • 那么下降链uu 的贡献即为 cnt2wudepucnt2_{w_u-dep_u}

但是有个问题就是路径 aba\to blca(a,b)\operatorname{lca}(a,b) 可能会被计算两次,所以aba\to b 既有上升链又有下降链我们就要规定 lca(a,b)\operatorname{lca}(a,b) 包含且仅包含在上升链中

还有一个问题就是 cnt2cnt2 的下标可能是负数,那么让下标整体加上一个大整数即可。

计算答案的过程还有一个细节,为了防止其它子树的贡献影响到 uu 的子树,所以需要这样写:

void dfs2(int u,int fa)
{
	int tmp=cnt[w[u]+dep[u]],tmp2=cnt2[w[u]-dep[u]+mov]; // 记录下其它子树的贡献
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa)
		{
			continue;
		}
		dfs2(v,u);
	}
	for(int val:st[0][u])
	{
		cnt[val]++;
	}
	for(int val:st[1][u])
	{
		cnt[val]--;
	}
	for(int val:st2[0][u])
	{
		cnt2[val+mov]++;
	}
	for(int val:st2[1][u])
	{
		cnt2[val+mov]--;
	}
	ans[u]=cnt[w[u]+dep[u]]-tmp+cnt2[w[u]-dep[u]+mov]-tmp2; // 容斥获得 u 子树的贡献
}