PROBLEM LINK: Tree and Unwanted leaves
Author: Sumeet Pachauri
Tester: Pankaj Sharma
Editorialist: Sumeet Pachauri
Difficulty:
Easy-Medium
Prerequisites:
Generic Trees, DFS
Problem:
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 
