题解

思路

把树任选一个顶点作为根。对于一次从 $u$ 到 $v$ 的旅行，设 $w$ 是 $u$ 与 $v$ 的最近公共祖先。我们在顶点上维护差分值：给 $u$ 和 $v$ 各加一，给 $w$ 减二。

完成所有旅行的差分标记后，按从叶子到根的顺序累加。对于任意非根顶点 $x$，其子树内差分值之和恰好等于连接 $x$ 与父亲的边被经过的次数。因此，只需把该和值写回这条边原来的输入编号。

最近公共祖先可以用倍增处理。

做法

先通过一次遍历求出每个顶点的父亲和深度，再建立 $2^j$ 级祖先表。对每次旅行查询最近公共祖先，并完成三个顶点上的差分修改。最后按照遍历顺序的逆序累加差分值，把每个非根顶点的累加结果写入它与父亲之间的原编号边。

正确性证明

考虑一条父子边 $(p,x)$。删除这条边后，树被分为顶点 $x$ 的子树和其余部分。一次旅行经过这条边，当且仅当它的两个端点恰有一个位于 $x$ 的子树中。

对一次端点为 $u,v$、最近公共祖先为 $w$ 的旅行加入差分后，在任意子树内求和：若两个端点都在子树内，则 $u,v$ 的两个正贡献与 $w$ 的两个负贡献抵消；若两个端点都不在子树内，总贡献为零；若恰有一个端点在子树内，则 $w$ 不在该子树内，总贡献为一。因此，顶点 $x$ 子树的差分和正好等于经过边 $(p,x)$ 的旅行数。

自底向上累加会求出每个子树的差分和，所以写入每条父子边的值均正确。按边的原输入编号输出，得到题目要求的答案。

复杂度分析

建立祖先表需要 $O(n\log n)$ 时间和 $O(n\log n)$ 空间。每次最近公共祖先查询需要 $O(\log n)$ 时间，最终累加需要 $O(n)$ 时间。总时间复杂度为 $O((n+k)\log n)$，空间复杂度为 $O(n\log n)$。