5 months ago

Arpan • 80

Noida

Approach:

We can solve this problem using dfs .As we want 1 to have the last value as g_nodes and value of all other nodes as 0,we will start our dfs from 1. When we  have traversed all the adjacent nodes of a particular node ,we return its current value to its parent where it will be added to value of parent. And as we have processed all the nodes and come out after traversing adjacent nodes of 1,we return to our main function.

//CODE:

#include <bits/stdc++.h>

using namespace std;

#define f(n, i, x) for (int i = x; i < n; i++)

#define vb push_back

#define ll long long

vector<vector<int>> list1;

vector<int> vis;

vector<int> level;

int ans = 0;

int dfs(int cur, int k)

{

    if (!vis[cur])

    {

        vis[cur] = 1;

        for (auto x : list1[cur])

        {

            level[cur] += dfs(x, k);

        }

        if (cur == 1)

            return 0;

        ans += ceil((1.0 * level[cur]) / k);

        return level[cur];

    }

    else

        return 0;

}

int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    int n, k;

    cin >> n >> k;

    list1.resize(n + 1);

    level.resize(n + 1, 1);

    vis.resize(n + 1, 0);

    int a[n];

    f(n - 1, i, 0) cin >> a[i];

    (n + 1);

    f(n - 1, i, 0)

    {

        int x;

        cin >> x;

        list1[a[i]].vb(x);

        list1[x].vb(a[i]);

    }

    int z = dfs(1, k);

    cout << ans << endl;

}

6 hours ago

a aryan • 0

Dhanbad

#include <bits/stdc++.h>

using namespace std;

void dfs(int v,int par,vector<int> &val,vector<vector<int>> &adj){

    for(int u:adj[v]){

       if(u==par)continue;

       dfs(u,v,val,adj);

        val[v]+=val[u];

    }

}

int main() {

    int k,n;

    cin>>k>>n;

    int e=n-1;

    vector<int>from(e),to(e);

    for(int i=0;i<e;i++){

        cin>>from[i];

    }

    for(int i=0;i<e;i++){

        cin>>to[i];

    }

    vector<vector<int>>adj(n+1);

    vector<int>val(n+1,1);

    for(int i=0;i<e;i++){

        adj[from[i]].push_back(to[i]);

        adj[to[i]].push_back(from[i]);

    }

    dfs(1,-1,val,adj);

    int min_step=0;

    for(int i = 2; i <= n; i++) {

        if(val[i]%k!=0){

            min_step+=val[i]/k;

        }

        min_step+=1;        

    }

    cout<<min_step<<endl;

}