Join Us
Loading Similar Posts
Entering edit mode
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;
}
Entering edit mode
#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;
}
efficient simple way i store the val of each node in val array that i will get while backtracking and then check for no.of steps required to make them 0(node 2 to node n)