先考虑 $O(nq)$ 做法。枚举每个点为根去 DFS 做 dp。

不难发现两个相邻的点不能操作二，所以状态要设 $f_{i,2}$ 表示点 $i$ 操作二，把子树的边覆盖完的最小操作。

若一个点不进行操作二，则他到子节点需要用操作一来覆盖，而一个操作一可能端点在两个儿子。考虑先把这个操作一的链拆开，然后从儿子向上合并时去匹配。设 $f_{i,1},f_{i,0}$ 表示点 $i$ 进行操作二，覆盖后子树内留下一个到儿子的操作一半条链没有匹配或全部匹配完。

然后考虑 dp 转移，分类讨论即可：

$$f'_{x,0}\gets \min(f_{x,0}+f_{y,2},f_{x,1}+f_{y,0},f_{x,1}+f_{y,1}-1)$$

$$f'_{x,1}\gets \min(f_{x,1}+f_{y,2},f_{x,0}+f_{y,1},f_{x,0}+f_{y,0}+1)$$

$$f'_{x,2}\gets f_{x,2}\min(f_{y,0},f_{y,1})$$

然后直接转移就可以，复杂度为 $O(nq)$。

考虑换根出答案？但是这个贡献形式比较难拆开，考虑用矩阵描述 dp 的转移，这样做前缀后缀的转移就转化为求矩阵前缀后缀积了，本来矩阵乘法需要严格控制顺序，但这个东西先合并那个子节点无所谓，所以瞎做就行。

复杂度为 $O(nV^3)$，其中 $V=3$。