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

为了方便下文描述,我们称深度递减的那一段为”上升链“,深度递增的那一段为”下降链“。
不难发现,对于路径 ,若 和 不是子孙关系,那么它的上升链为 ,下降链为 ,否则就只有上升链或下降链 。
那么考虑对上升链和下降链分别计算答案,最后加起来:(定义 为节点 的深度)
-
对于上升链:
- 因为起点为 的上升链能被 观察到当且仅当 ,移项得 ;
- 所以可以在 dfs 的同时用 表示满足 且这条上升链经过 的上升链的起点 的个数;
- 那么上升链对 的贡献即为 。
-
对于下降链:
-
令 表示这条下降链的开始时间,因为一个人要跑完上升链才会去跑下降链;
-
因为起点为 的下降链能被 观察到当且仅当 ,移项得 ;
-
所以可以在 dfs 的同时用 表示满足 且这条下降链经过 的下降链的起点 的个数;
-
那么下降链对 的贡献即为
-
但是有个问题就是路径 的 可能会被计算两次,所以若 既有上升链又有下降链我们就要规定 包含且仅包含在上升链中。
还有一个问题就是 的下标可能是负数,那么让下标整体加上一个大整数即可。
计算答案的过程还有一个细节,为了防止其它子树的贡献影响到 的子树,所以需要这样写:
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 子树的贡献
}