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

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

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

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

那么考虑对上升链和下降链分别计算答案，最后加起来：（定义 $dep_u$ 为节点 $u$ 的深度）

• 对于上升链：

  • 因为起点为 $v$ 的上升链能被 $u$ 观察到当且仅当 $dep_v-dep_u=w_u$，移项得 $dep_v=w_u+dep_u$；
  • 所以可以在 dfs 的同时用 $cnt_i$ 表示满足 $dep_v=i$ 且这条上升链经过 $u$ 的上升链的起点 $v$ 的个数；
  • 那么上升链对 $u$ 的贡献即为 $cnt_{w_u+dep_u}$。

• 对于下降链：

  • 令 $stme_v$ 表示这条下降链的开始时间，因为一个人要跑完上升链才会去跑下降链；

  • 因为起点为 $v$ 的下降链能被 $u$ 观察到当且仅当 $dep_u-dep_v=w_u-stme_v$，移项得 $stme_v-dep_v=w_u-dep_u$；

  • 所以可以在 dfs 的同时用 $cnt2_i$ 表示满足 $stme_v-dep_v=i$ 且这条下降链经过 $u$ 的下降链的起点 $v$ 的个数；

  • 那么下降链对 $u$ 的贡献即为 $cnt2_{w_u-dep_u}$

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

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

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

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 子树的贡献
}