计算为树分配权重的方法，使得 w1 <= w2 <= ... <= wm

Question

问题：

给定一棵具有 N 个节点 的树和来自该树的 M 对节点 的数组，这些对从 1- >m.

有w[i]作为对2取模后节点对之间路径上的权重之和。所以w[i] 可以是 0 或 1。

计算为树分配权重的方法，使得 w1 <= w2 <= ... < = wm

权重只能是1或2

约束条件：

N, M <= 30000

示例：

图表：

M对节点：

1 2
2 3
1 3

答案：2

解释：

以下是分配边的所有可能方式：

方式一：

Edge: 1 - 2 weight: 1
Edge: 1 - 3 weight: 1 

w[] would be {1, 1, 0}
-> Not valid

方式二：

Edge: 1 - 2 weight: 1
Edge: 1 - 3 weight: 2 

w[] would be {1, 0, 1}
-> Not valid

方式三：

Edge: 1 - 2 weight: 2
Edge: 1 - 3 weight: 1 

w[] would be {0, 1, 1}
-> Valid

方式四：

Edge: 1 - 2 weight: 2
Edge: 1 - 3 weight: 2 

w[] would be {0, 0, 0}
-> Valid

其他有效的w[]如{0, 0, 1}或{1, 1, 1}不计为答案，因为没有办法分配权重得到上面的数组。

我对 O(2^N * M) 的看法：

到目前为止，我最好的解决方案是为图形生成所有可能的权重分配并检查它是否有效。这显然不是最好的方法。

是否有任何提示或关键字可以帮助我找到针对此问题的优化解决方案？

P/S:抱歉我的英语不好，如果有什么需要澄清的请评论

Answer 1

相关知识体系是有限域上的线性代数具有两个元素 (GF(2))，并且特别是图形同源性。

给定边权重，表示一组向量的函数 GF(2) 中这些边的总权重的边是一个线性映射。
A到B的树路径与从B到C的树路径是从A到C的树路径。

设 G 是其边为 m 给定对的图。对于每个有效 w向量，我们可以在G中使用深度优先搜索来统计有效的解决方案。正确性来自秩无效定理。

在G的每个连通分量C中，深度优先搜索根在某个节点 r，我们为 C 中的每个节点 x 记录以下总和的奇偶性从 r 到 x 的边权重。每当我们找到一个树弧，我们就可以计算头部的奇偶性来自尾部的奇偶性。每当我们发现一个 back arc，我们可以做同样的事情，但是头部已经有一个平价。如果双方意见不一致，那么这个问题就没有解决方案了 w.

每条树弧对应一个独立的方程，所以通过 rank-nullity，若有解则有2^n−1−k 其中，k 是树弧的数量。

计算为树分配权重的方法，使得 w1 <= w2 <= ... <= wm

Count ways to assign weights for a Tree so that w1 <= w2 <= ... <= wm

algorithm

tree