PROBLEM LINK:
Author: Sandeep SIngh
Tester: Arkaprabha Ghosh
Editorialist: Sandeep Singh
DIFFICULTY:
EASY
PREREQUISITES:
dfs
QUICK EXPLANATION:
Find the number of nodes at each level using dfs. Then find the level with maximum nodes.
EXPLANATION:
Each village is a node in the tree. On the first day, only one clone exists (in the village 1). The next day, that clone multiplies itself and all clones thus formed go 1 level down. In a similar manner, on each day, the clones keep going 1 level down. Hence, On i^{th} day, all clones are on the i^{th} level.
Now we know that on i^{th} day, all clones are on the i^{th} level. To find the number of clones, realise that all nodes on a level will have exactly 1 clone. Thus the number of clones at a level is equal to the number of nodes at a level.
Hence we just need to find the the level with the max nodes. In case two or more levels have max nodes, as per the question we need to print the one with lower level.
snippet for the dfs part is given below:
void dfs(int u, int h, int p=0) {
ht = max(ht, h);
++nodes[h];
for(int v : G[u]) {
if(v != p)
dfs(v, h+1, u);
}
}
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
vector<int>g [100005];
int maxlvl;
int nodes[100005];
void dfs(int u,int p,int level){
maxlvl=max(maxlvl,level);
nodes[level]++;
for(int child:g[u]){
if(child!=p){
dfs(child,u,level+1);
}
}
}
using namespace std;
void solve(){
int N,t,i,x,y;
cin>>N;
for(i=1;i<N;i++){
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1,0,1);
int day=0;
ll mxcl=0;
for(i=1;i<=maxlvl;i++){
if(nodes[i]>mxcl){
mxcl=nodes[i];
day=i;
}
}
cout<<day<<endl;
}
int main() {
int T =1;
//cin>>T;
while(T--)
solve();
return 0;
}
Tester's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define ppb pop_back
#define pii pair<ll, ll>
#define vi vector<ll>
#define vull vector<ull>
#define vpii vector<pii>
#define mt make_tuple
#define ff first
#define ss second
#define uset unordered_set
#define umap unordered_map
#define all(x) x.begin(), x.end()
#define revall(x) x.rbegin(), x.rend()
#define rep(i, j, k) for(ll i = j; i < (k); ++i)
#define repr(i, j, k) for(ll i = k-1; i >= (j); --i)
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define T int tt; cin>>tt; while(tt--)
const ll MOD = (ll)(1e9+7);
const int inf = (int)INFINITY;
const ll INF = (ll)INFINITY;
const int MAX = (int)(1e5+5);
vi primes;
ll nI[MAX],fI[MAX],fact[MAX];
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
ll gcd(ll a,ll b){while(b){ll t=a;a=b;b=t%b;}return a;}
ll lcm(ll a,ll b){return (max(a,b)/gcd(a,b))*min(a,b);}
bool isPrime(ll n){if(n<=1)return 0;if(n<=3)return 1;if(n%2==0||n%3==0)return 0;for(ll i=5;i*i<=n;i+=6)if(n%i==0||n%(i+2)==0)return 0;return 1;}
void find_primes(ll n = 100000000){ll limit=floor(sqrt(n))+1;vi test;test.pb(2),primes.pb(2);for(ll i=3;i<limit;i+=2)if(isPrime(i))test.pb(i),primes.pb(i);ll lo=limit,hi=2*limit;bool p[limit];while(lo<n){if(hi>n)hi=n;
memset(p,true,sizeof(p)); for(int i=0;i<test.size();++i){ll mn=(lo/test[i])*test[i];if(mn<lo)mn+=test[i];for(ll j=mn;j<hi;j+=test[i])p[j-lo]=0;}rep(i,0,limit)if(p[i] && i+lo<hi)primes.pb(i+lo); lo+=limit,hi+=limit;}}
ll modmult(ll a,ll b){ll res=0;a%=MOD;while(b){if(b&1)res=(res+a)%MOD;a=(a<<1)%MOD;b>>=1;}return res;}
ll modexpo(ll a,ll b){ll res=1;a%=MOD;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll nCr(ll n,ll r){ll res=1;if(r>n>>1)r=n-r;rep(i,0,r){res=(res*(n-i))%MOD;res=(res*modexpo(i+1,MOD-2))%MOD;}return res;}
void binomial_pre(){nI[0]=nI[1]=fI[0]=fI[1]=fact[0]=1;rep(i,2,MAX)nI[i]=nI[MOD%i]*(MOD-MOD/i)%MOD;rep(i,2,MAX)fI[i]=(nI[i]*fI[i-1])%MOD;rep(i,1,MAX)fact[i]=(fact[i-1]*i)%MOD;}
ll binomial(ll n,ll r){if(n<r)return 0;return ((fact[n]*fI[r])%MOD*fI[n-r])%MOD;}
vi G[MAX], nodes(MAX);
int ht;
void dfs(int u, int h, int p=0) {
ht = max(ht, h);
++nodes[h];
for(int v : G[u]) {
if(v != p)
dfs(v, h+1, u);
}
}
int main() {
fastio;
//find_primes();
//binomial_pre();
#define JUDGE
#ifndef JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
//T {
int n;
cin >> n;
rep(i, 1, n) {
int u, v;
cin >> u >> v;
G[u].pb(v);
G[v].pb(u);
}
ht = 0;
dfs(1, 1);
int res = 0, mx = 0;
rep(i, 1, ht+1) {
if(nodes[i] > mx) {
mx = nodes[i];
res = i;
}
}
cout << res;
cout << endl;
//}
return 0;
}