(2022 Niu Ke Duo School 5) D-Birds in the tree (tree DP)

Title:

Sample input:

710111111 21 3twenty four3 52 64 7

Sample output:

28

The meaning of the question: Given a tree of n nodes, and the color of each node on the tree is 0 or 1, ask how many subtrees have all the leaves of the same color in the end.

Analysis: Let f[i][0] represent the degree 1 (excluding the root node) in the subtree rooted at the i-th nodeThe number of subtrees whose point color is 0, f[i][1] represents the number of subtrees whose degree is 1 (excluding the root node) in the subtree with the i-th node as the root., first explain the meaning of the array:

For this image, obviously

f[4][0]=0,f[4][1]=1

f[3][0]=1,f[3][1]=0

f[2][0]=1,f[2][1]=0

And what about point one?Is it the number of legal states, that is, f[1][1]=2, f[1][0]=1, it is not, it is actually f[1][1]=2, f[1][0]=3

Note that our f arrayonly has clear requirements for the color of nodes with degree 1 other than the root node of the current subtree, and there is no requirement for the root node, so 1-2, 1-3 are also considered in f[1][1], of course, this is not legal, but this situation is useful for updating the parent node above, such as 1The parent node of 5 is 5, then if the color of 5 is 0, then a subtree can be formed by 5-1-2, and the color of the node with the satisfaction degree of 1 is the same.Of course, We must subtract the impact of this illegal situation when we count the answers, this illegal situationHow many are there?In fact, statistics are better, because the degree of the root node of the subtree formed in this case is 1, which means that it will only extend in the direction of one of his child nodes. If the color of the root node is 1, then how many child nodes j there areThere will be as many illegal situations as f[j][0]. The sum of f[j][0] of all child nodes j is allis illegal.But you will find that 2-1-3 in the subtree rooted at 1 is a legal subtree, so how do we consider this situation?In fact, it is very simple. For example, for the above figure, the current subtree root node No. 1 node has 3 child nodes, then For each child j can contribute fOne of [j][0] legal schemes, of course, you can also not contribute, so there will be f[j][0]+1 legal schemes in total, then this is the case for all child nodes, we finallyIt only needs to find a product according to the multiplication principle, but this will also bring a problem, such as what if all my child nodes do not contribute?Because we have initialized the record in this case at the beginning, so at this time we need to subtract 1 from the answer, which corresponds to the case where we do not select in all subtrees. Finally, don't forget that we need to count theThe subtree with the current node as the root contains the root node of the current subtree and the degree of the root node of the current subtree is 1. We need to exclude this situation. I have analyzed the calculation method just now. For details, seeCode:

#include#include#include#include#include