CF833D Red-Black Cobweb

题意 ： 给定一棵 个节点的树，边有黑白两色和权值。

求满足黑白边的比例在 内的路径边权乘积的乘积。

答案对 取模。

，时限 。

---

考虑点分治。

对于一条从根出发的路径，记为 ，表示黑边有 个，白边有 个，权值乘积为 。

两条路径 合并后合法的充要条件是 。即 这转化为了二维偏序问题，在点分治中，可以分治套分治处理，但较为繁琐。

注意到 和 只能有一条成立，故不可能同时违反上述两个条件。

于是可以分别计算两种违反的贡献，然后除去即可。或者可以用满足第一条的贡献除以违反第二条的贡献。

减少了一个维度，复杂度可以轻松做到 。