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.