Node Marking Codechef Solution

by

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

Subtasks

  • 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];
}
 

void google(){
    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();
       
    }
}

Weekly Contest 247

Biweekly Contest 55

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Related :

Related :

Leave a Comment

19 − three =