题解

思路推导

为每个顶点维护一个标记，表示最近一次覆盖该顶点的第一类操作编号，初始标记为零。一次第一类操作把路径上的所有顶点标记为同一个新的编号。

考虑任意边 $(u,v)$。若本次操作路径同时包含两个端点，它会在最后一步变为重边，两个端点也得到相同的新标记；若路径只包含一个端点，该边会在清空阶段变为轻边，两个端点标记不同；若两个端点都不在路径上，边的状态与端点标记关系都不变。因此一条边为重边，当且仅当两个端点的标记相同且不为零。

问题转化为树上路径赋值和路径统计：把一条路径上所有顶点赋成同一个新值，查询路径上相邻顶点标记相同且非零的边数。

做法

使用重链剖分把任意树上路径拆成若干个连续的深度优先序区间。在线段树节点中维护区间最左标记、最右标记，以及区间内部相邻且标记相同非零的位置数量。合并相邻区间时，除两侧内部答案外，只需判断左区间最右标记与右区间最左标记是否相同且非零。

线段树支持区间赋值。一个长度为 $L$ 的区间被赋为正标记后，内部恰有 $L-1$ 条满足条件的相邻边。

路径查询时要保留方向。处理两个端点所在的不同重链时，一侧取得的区间需要反转，另一侧需要前置合并；进入同一重链后再合并最后一段。最终聚合信息中的相邻相等数量就是答案。

每组数据都重新建立树、剖分数组和线段树，避免不同数据组之间遗留状态。

正确性证明

根据标记定义和第一类操作的顺序，任意时刻边为重边当且仅当两端点标记相同且非零。重链剖分把查询路径分成若干个互不重叠、按路径顺序首尾相接的区间。线段树准确记录每个区间内部满足条件的相邻对；合并时额外检查唯一跨越两区间边界的相邻对，因此合并结果准确表示两区间连接后的路径。按真实方向依次合并全部区间后，统计值恰为原树路径上的重边数。

路径赋值覆盖且仅覆盖操作指定路径上的全部顶点，所以标记模型与原操作始终一致。故所有询问答案正确。

复杂度分析

重链剖分把一条路径拆成 $O(\log n)$ 个区间，每次线段树操作耗时 $O(\log n)$。单次操作时间复杂度为 $O(\log^2 n)$，每组数据空间复杂度为 $O(n)$。