There exist a rooted tree with n nodes, in each operation on the tree: all leaf nodes with count in a multiple of 3 and with the same parent node are removed. Also if all children of a parent are removed it becomes a new leaf node and the operation is again repeated until the operation can not be performed. The number of nodes finally left on tree after all operations is the required answer.
Explanation:
Keenly observing the question we just need to use a count for each node and add the nodes which
are a leaf node
are a potential leaf node(they will turn into a leaf node, after one or more operations) under the condition that the leaf nodes and potential leaf nodes are originating from same parent.
Identifying potential leaf node: If the count calculated above is equal to the total child nodes of a parent node and is a multiple of 3, then this parent node is a potential leaf node.
If count is not a multiple of 3 it is assigned a number which is a multiple of 3 and is also the maximum possible such number lesser than count
Sum of count of all nodes can be saved in a counter.
Subtracting the value in counter from the total nodes will give the required answer, the nodes finally left on the tree.
DFS: Applying dfs on root node which is given as 1, and moving to adjacent nodes until a leaf node is reached, and then backtracking to repeat it for other leafs too. For each parent under consideration, declaring count variable and counting leaf or potential leaf nodes. Encountering leaf node or potential leaf node, returns 1 otherwise 0 is returned.
Solution:
Setter's Solution
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define r0 return 0
#define test int T; cin>>T; while(T--)
vector<int> tree[100001];
int cnt;
//this function follows dfs approach
int cntleaves(int n)
{ // leaf node, return 1 to its counter
if(tree[n].size()==0)
return 1;
else
{ //counter for the current node under consideration
int count=0;
for(int i=0;i<tree[n].size();i++)
{
count+=cntleaves(tree[n][i]);
}
//counted leafs and potential leafs sum up to the total child nodes,
//hence node under consideration is a potential leaf node, and returns 1 to its counter
if(count%3==0&&tree[n].size()==count)
{ cnt+=count;
return 1;
}
//all other cases won't cause current node to be a potential leaf node, hence returns 0
//if count is greater than or equal to 2, the Unwanted leafs are counted out of
//the variable 'count' and removed
else
if(count>2)
{
int temp=count/3;
cnt+=(temp*3);
return 0;
}else
return 0;
}
}
void solve()
{
for(int i=0;i<100001;i++)
tree[i].clear();
int n;
cin>>n;
tree[0].push_back(-1);
for(int i=1;i<n;i++)
{
int x;
cin>>x;
tree[x].push_back(i+1);
}
cnt=0;
// cntleaves either return 1 or 0, if it is 1 then root node is itself either a leaf or potential leaf node
if(cntleaves(1))
cout<<"1\n";
else
cout<<n-cnt<<"\n";
}
signed main(){
fastio
test
solve();
r0;
}
Please give me suggestions if anything is unclear so that I can improve. Thanks
@kaalbhairav01 Hi In Question :
(i) For each parent node(which has a valid leaf node attached to it). Can u explain valid leaf nodes means?
(ii) If a parent has all its leaf nodes cut, only then the parent node itself becomes a new leaf node. (from this what I understand is count only leaf nodes and if the count of the leaf node is multiple of 3 then parent also become new leaf but in the editorial problem statement says if all children of a parent are removed it becomes a new leaf node which means I have to check non leaf node also ).
can u explain why my understanding is wrong
You can see that in the problem statement, leaf node was defined as the one, with no outgoing edges
“if a parent has all its leaf nodes cut”, this is the source of confusion I assume, carefully reading further and to full, the question provides every non leaf node a scope to convert itself into a leaf node. The counting of any non leaf node can not be skipped as such because there would be no guarantee if it had the capability to turn into a leaf node. Hence if you have checked all child nodes of a parent to see if a non leaf node can become leaf, only then will you know the actual number of leaf nodes. We require a strong basis to not take into account a node which is non leaf, which can’t be obtained without checking it. Now after confirming all nodes which are “actually leaf”, we can count them and if this count is a multiple of 3, all of them will be removed, so in this case all child nodes are being removed, and all child nodes were leaf nodes too.
Also see the explanation to sample testcase, for better clarity, you can also think of a sudoku or minesweeper, where you must be sure before taking the decision. Same goes with ignoring a non leaf node.
Hope it helps
Thanks man.one point
for example, a parent node with child nodes is (1 leaf and 2 potential leaf nodes and 2 non-leaf nodes(its child node are not multiplies of 3 )). this information I will get doing dfs on parent node . now what I’m doing is counting leaf node and potential leaf node (1+2 = 3) so 3 multiply of 3 so I’m considering parent as a potential leaf node.
But after reading the editorial, what I got is, for that parent 2 non-leaf child node are present so parent cannot be a new leaf node or potential leaf node
Hey brother, I recognise the confusion you are referring to, and that is why the case similar to the one you wrote was shown in the explanation which might be you have missed out, here
Consider node 4 which had 3 nodes removed but was not considered a leaf because it still had a outgoing edge. “If a parent has all its leaf nodes cut, only then the parent node itself becomes a new leaf node” the line is the next parameter for any parent node to satisfy, it nowhere demurs the basic definition of leaf node- which has no outgoing edges as written in the problem statement, i hope the explanation image above clarifies it in the question
Hi, have you uploaded the Editorials for ECPC10E, ECPC10F and ECPC10G? If not, could you please upload it? If yes, could you please provide the link? I am not able to find them.
Thanks
Hey there @shashank2409 , Those three editorials are underway and will be posted as soon as possible, the same will be notified on the Contest Invitation post too. The delay has occured due to the sudden ill health of the setter cum editorialist, we hope the wait will be worth
I’m thinking about a solution where I would find the level of every nodes, then going up level by level from the leaf nodes, calculating how many nodes will be deleted and which parent will no longer be parent node, would this work ?
@bubu2006, as i see that, it’s a straight forward dfs approach ques, however what you wrote sounds exactly what needs to be done, it depends on your implementation, you can try that
