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

user_9920930 0
Viewed 101

Question:

Given a tree with N nodes and an array of M pairs of nodes from that tree, the pairs are indexed from 1->m.

Have w[i] as the sum of weights on the path between the pair of nodes after modulo by 2. So w[i] can either be 0 or 1.

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

The weights can only be 1 or 2.

Constraints:

N, M <= 30000

Example:

The graph:

example graph

The M pairs of nodes:

1 2
2 3
1 3

Answer: 2

Explaination:

Here are all the possible ways to assign edges:

Way 1:

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

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

Way 2:

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

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

Way 3:

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

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

Way 4:

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

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

Other valid w[] such as {0, 0, 1} or {1, 1, 1} is not counted as an answer because there are no way to assign weights to get the above arrays.

My take on O(2^N * M):

My best solution so far is to generate all possible weight assignments for the graph and check if it's valid. Which is clearly not the best way.

Is there any hint or keyword that can help me find out an optimized solution for this problem?

P/S: Sorry for my bad English, please comment if anything needs to be clarify

tree algorithm
1 Answers

The relevant body of knowledge is linear algebra over the finite field with two elements (GF(2)), and graph homology specifically.

  • Given edge weights, the function from a vector representing a set of edges to the total weight of those edges in GF(2) is a linear map.

  • The XOR (that is, sum in GF(2)) of the tree path from A to B and the tree path from B to C is the tree path from A to C.

Let G be the graph whose edges are the m given pairs. For each valid w vector, we can use depth-first search in G to count the number of valid solutions. Correctness follows from the rank–nullity theorem.

In each connected component C of G, which the depth-first search roots at some node r, we record for each node x in C the parity of the sum of edge weights from r to x. Whenever we find a tree arc, we can compute the parity of the head from the parity of the tail. Whenever we find a back arc, we can do the same, but the head already has a parity. If the parities disagree, then there are no solutions for this particular w.

Each tree arc corresponds to an independent equation, so by rank–nullity, if there is any solution, then there are 2n−1−k of them, where k is the number of tree arcs.

user_21446690
Related