思路

这道题思路很妙。

发现算子只有\(+, -, \times\)，所以路径上的解可以表示成线性组合：\(ax + b\)。我们记录从根到下、从下到根的线性组合前缀，然后我们考虑来利用前缀进行分割：就是树上差分的那种套路。

我们先考虑父亲边为：

• 加法/减法：从根向下直接加上即可，从下到根也直接加上就好，但是需要乘上之前的\(a\)。
• 乘法：从根到下需要把\(a\)乘上，\(b\)加上乘积；但是如果是向上合并的话，就可以直接把\(a\)乘上就行：因为反向而言只对乘项有关。

大概这样合并：

void dfs(int u)
{
	dep[u] = dep[fa[0][u]] + 1;
	for (int i = head[u]; i != -1; i = edges[i].nxt)
		if (edges[i].to != fa[0][u])
		{
			fa[0][edges[i].to] = u, upweight[edges[i].to] = edges[i].weight;
			trs_up[edges[i].to] = trs_up[u], trs_down[edges[i].to] = trs_down[u];
			if (edges[i].weight == 1)
			{
				trs_down[edges[i].to].b = (trs_down[edges[i].to].b + vi[edges[i].to]) % mod;
				trs_up[edges[i].to].b = (1LL * trs_up[u].a * vi[u] + trs_up[u].b) % mod;
			}
			else if (edges[i].weight == 2)
			{
				trs_down[edges[i].to].b = (trs_down[edges[i].to].b - vi[edges[i].to] + mod) % mod;
				trs_up[edges[i].to].b = (1LL * trs_up[edges[i].to].b - 1LL * trs_up[u].a * vi[u] % mod + mod) % mod;
			}
			else
			{
				trs_down[edges[i].to].a = 1LL * trs_down[u].a * vi[edges[i].to] % mod;
				trs_down[edges[i].to].b = 1LL * trs_down[u].b * vi[edges[i].to] % mod;
				trs_up[edges[i].to].a = 1LL * trs_up[edges[i].to].a * vi[u] % mod;
			}
			dfs(edges[i].to);
		}
}

如何分裂边呢？我们只需要抵消掉\(a\)和\(b\)的效果即可，直接用逆元和减法就行了：考虑设置\(ax + b\)为从\(x\)到根的效果，设置\(cx + d\)为\(lca\)到根的效果，那么\(x\)到根的效果为\(ex + f\)，可以列式为：

\[ e(cx + d) + f = ax + b \]

解出来就行了，然后再对\(y\)做差不多的处理就可以解决这道题了。（挺麻烦的，细节还挺多，不如打暴力）

Continue reading →