MapleTreeEasy
SRM 799 · 2021-02-04 · by IH19980412
Problem Statement
Kaede loves maple trees. One day, she found a big maple tree and she described it as an undirected connected graph with N nodes and N-1 edges.
You are given the description in the
There are 2N-1 ways to choose a non-empty subset of nodes. Once we choose a subset of nodes, there is always a unique minimal subtree which contains all nodes in the subset.
Kaede got interested in thin subsets of nodes. A non-empty subset of nodes is called thin if the corresponding minimal subtree contains no nodes of degree 3 or more.
Please help Kaede: calculate and return the exact number of thin subsets of nodes for the given tree.
Notes
- A subtree is any subgraph that is itself a tree.
- The minimal subtree (among all subtrees that contain the chosen subset of nodes) is the unique subtree with the smallest number of nodes.
Constraints
- N will be between 2 and 50, inclusive.
- p will contain exactly N-1 elements.
- For each valid i, p[i] will be between 0 and i, inclusive.
{0, 1, 2, 3}
Returns: 31
This tree looks as follows: 0 \ 1 \ 2 \ 3 \ 4 Clearly, any non-empty subset of its nodes is thin.
{0, 1, 0, 3}
Returns: 31
This tree looks as follows: 0 / \ 1 3 / \ 2 4 It is essentially the same tree as in the previous example, the only difference is that now we chose its middle node as the root. The answer is still the same: each non-empty subset of its nodes is thin.
{0, 0, 0, 0, 0, 0}
Returns: 43
There are the following thin subsets of nodes: 1: Only the root (node 0) and nothing else. 6: The root and one of the leaves. 15: The root and two of the leaves. 6: One of the leaves. 15: Two of the leaves. That is a total of 43 thin subsets. No other subset is thin. As soon as we select at least three distinct leaves, the minimal subtree containing the selected nodes will contain node 0 and edges from this node to all selected leaves. Thus, in the minimal subtree there will be a node of degree at least 3.
{0,0,0,0,3,4,6,7,4,5,2,8,5,9,14,14,13,0,16,8,5,2,19,6,6,17,18,16,9,16,6,25,11,12,0,21,0,13,15,24,28,7,19,38,31,16,29,39}
Returns: 81999
{0,0,0,3,3,2,6,7,1,6,1,11,12,6,0,15,16,7,8,8,7,18,18,9,10,2,6,21,17,20,29,27,21,15,4,23,21,33,30,6,24,31,3,28,21,29,44}
Returns: 120961
{0, 0, 1, 1, 2}
Returns: 49
0 / \ 1 2 / \ \ 3 4 5
Submissions are judged against all 53 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MapleTreeEasy with a public method long long count(vector<int> p) · 53 test cases · 2 s / 256 MB per case