chemistry 思考题

Hydrocarbon

Ninetail is building a tree.

She has N nodes and she will assign a value from 0 to 3 to each node. All nodes with the same value are indistinguishable.

Then she will connect the N nodes with N-1 edges so that they form a tree. She will also assign a value from 1 to 3 to each edge.

Unfortunately, she doesn't realize the nodes she is using are bombs!!! For any node u, if the sum of the value of the node and all the edges connected to it isn't 4, i.e. v_u+\sum_{(x,y,w)\in E}(([x=u]+[y=u])\times w) \neq 4, it will explode and Ninetail will die!!!

Moreover, if \sum_{u\in V}v_u\neq M where M is a given integer the tree will fall apart and explode.

After surviving the bomb attack, Ninetail wonders how many different trees are there.

Multi-task

If you can output whether there is a tree that meets the given requirement, you can get 20% of the score.
If you can output any of the possible tree structures, you can get another 30% of the score.
If you can print the number of different trees, you can get the rest 50%.

Note

A possible answer for N=3,M=6 is
(2)-2-(1)-1-(3)

Note that
(2)-2-(1)-1-(3) and (3)-2-(1)-1-(2) are considered the same.