思路
这道题思路很妙。
发现算子只有\(+, -, \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\)做差不多的处理就可以解决这道题了。（挺麻烦的，细节还挺多，不如打暴力）