# Node Marking Codechef Solution

## Node Marking Solution Problem Code: NDMRK

You are given an integer KK and a tree of size NN, rooted at node 11. In one operation, you can either select a node of the tree and color its entire subtree or create a new (uncolored) copy of the given tree. Find the minimum number of operations required so that the total number of colored nodes among all trees is exactly KK.

### Input

• The first line contains an integer TT, denoting the number of test cases. Then TT test cases follow.
• For each test case, the first line contains two integers NN and KK, the size of the given tree and the number of nodes to be colored, respectively.
• The next line contains N−1N−1 integers p2,…,pnp2,…,pn, where pipi is the parent of node ii.

### Output

For each testcase, output a single integer: the minimum number of operations required to color exactly KK total nodes.

### Constraints

• 1≤T≤4001≤T≤400
• 1≤N≤5⋅1041≤N≤5⋅104
• 1≤K≤1031≤K≤103
• 1≤pi≤N1≤pi≤N
• The input describes a valid tree rooted at node 11
• The sum of N⋅KN⋅K over all test cases does not exceed 107107

• Subtask 1 (10 points): The tree is a simple path
• Subtask 2 (35 points): 1≤N,K≤2001≤N,K≤200 and the sum of N⋅KN⋅K does not exceed 4⋅1044⋅104
• Subtask 3 (55 points): Original constraints

### Sample Input

``````2
3 5
1 1
4 6
1 2 2
``````

### Sample Output

``````4
3
``````

### Explanation

For the first test case:

• Operation 11: The subtree of node 11 is colored (coloring a total of 33 nodes).
• Operation 22: A new copy of tree is generated.
• Operation 33: The subtree of node 22 of the new tree is colored.
• Operation 44: The subtree of node 33 of the new tree is colored.

For the second test case:

• Operation 11: The subtree of node 22 is colored (coloring a total of 33 nodes).
• Operation 22: A new copy of tree is generated.
• Operation 33: The subtree of node 22 is colored (coloring a total of 33 more nodes).

Program:

``````#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;

#define ll long long int
#define fo(i,n) for(i=0;i<n;i++)
#define f0(i,k,n) for(i=k;i<n;i++)
#define fr(i,k,n) for(i=k-1;i>=n;i--)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define si(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ss(s) scanf("%s",s)
#define pi(x) printf("%d\n",x)
#define pl(x) printf("%lld\n",x)
#define ps(s) printf("%s\n",s)
#define setbits(x) __builtin_popcountll(x)
#define endl '\n'
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x,y) cout << #x << "=" << x << "," << #y << "=" << y <<endl
#define pb push_back
#define mk make_tuple
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define MI INT_MIN
#define MX INT_MAX
#define gcd(x,y) __gcd(x,y)
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it,a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.145926535897932384626
#define inf 1e18
#define sp(x,y) fixed<<setprecision(x)<<y
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
typedef priority_queue<int, vector<int>,greater<int> > pqri;
typedef priority_queue<ll, vector<ll>,greater<ll> > pqrl;
typedef priority_queue<int> pqi;
typedef priority_queue<int> pql;
typedef pair <int,int> pii;
typedef pair <ll,ll> pll;
typedef vector <int> vi;
typedef vector <ll> vl;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
typedef vector <vi> vvi;
typedef vector <vl> vvl;
typedef stack <int> sti;
typedef stack <ll> stl;
typedef queue <int> qi;
typedef queue <ll> ql;
typedef map<int,int> mpi;
typedef map<ll,ll> mpl;

const int mod = 1'000'000'007;
const int N = 3e5, M=N;

int p=1;

ll pw(ll n,ll a)
{
ll ans = 1;
while(a)
{
if(a&1)
ans = (n*ans)%mod;
n = (n*n)%mod;
a>>=1;
}
return ans;
}
ll modInv(ll n, ll p)
{
return pw(n, p - 2);
}

bool prime[10000001];
int call[10000001];
void Sieve(int n)
{
memset(prime, true, sizeof(prime));

for (int p = 2; p * p <= n; p++)
{
if (prime[p] == true)
{
for (ll i = p * p; i <= n; i += p)
prime[i] = false;
}
}

for(ll i=2;i<=n;i++)
if(prime[i])call[i]=call[i-1]+1;
else call[i]=call[i-1];
}

ll i,j,k,m,n,x,y,z,mi,mx,count=0,ans=0;

cout<<"Case #"<<p<<": "<<ans<<endl;
p++;

}
void solve(){
ll i,j,k,m,n,x,y,z,mi,mx,count=0,ans=0,sum=0;
cin>>n>>k;
for(i=0;i<n-1;i++)
{
cin>>x;

}
cout<<1<<endl;
}

int main() {
fast();
// Sieve(10000000);
int t = 1;
cin>>t;
while(t--) {
solve();

}
}``````