PROBLEM LINK:
PRACTICE
Editorialist: Indrajit Kabiraj
DIFFICULTY:
Medium
PREREQUISITES:
Graphs, dfs
PROBLEM:
Chef loves to travel and he wants to travel as far as he can.
Recently he landed in a country called Chefland.
Now there are many states in the country connected by a bi-directional bridge which connects State A to State B(There is no cycle).
Chef bought a car and he is running out of time and money so he bought K litres of fuel to travel.
Now chef wants to cover the longest path from an state A to state B and as he travels from an state U to V(if there is bridge between U and V) fuel reduces by a litre(If he had X litres of fuel before travelling from U to V then after it becomes X-1 litres).
If K litres is not sufficient to cover the longest path then he can’t travel.
Determine if it is possible to cover the longest path.
If K is not sufficienct to cover the longest path then print the minimum litres of fuel required to cover rest of the path else Print 0.
Note: There is no cycle.
Input:
The first line of the input contains two space-separated integers N and K,denoting the number of States and next N-1 lines contains contains two space-separated integers u and v, denoting State u and State v are Connected by bridge.
Output:
Print 0,If K litres is sufficient to cover the longest path.
else,Print the Litres of fuel required to cover rest of the path.
Constraints:
2<=N<=1000
1<=K<=1000
Example 1:
Input:
4 4
3 1
1 2
3 4
Output:
0
Note-> Chef can travel from State 2 to State 4 and 3 litres is required to travel from State 2 to State 4 which is lesser than K(i.e 4).
Example 2:
Input:
6 2
1 2
4 1
4 5
6 1
2 3
Output:
2
Note-> Chef can travel from State 3 to State 5 and 4 litres is required to travel from State 3 to State 5 which is greater than K(i.e 2) and 2 litres is required to cover the path.
EXPLANATION:
As all the cities are connected by an bidirectional bridge and there is no cycle we can consider the country as a tree with (n-1) edges.
Here, we are asked to find the longest path in the tree. So, we need to find the diameter of the tree(Diameter is the maximum distance between a pair of nodes).
Now, we have to check if K is greater than the diameter of not.If it is then the answer is 0 otherwise k-diameter.
Approach:-
- Pick any vertex as a source vertex.
- Then find the distant of each vertex from the source. It can find using DFS and keeping the distance count for each vertex from the source.
- Pick the vertex with maximum distance, and repeat step 2.
- Distance between the source and the the most distant vertex from the source is diameter.
SOLUTION:
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define FASTANDFURIOUS ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define For(i,n) for(ll i=0;i<n;i++)
#define MAX 200005
using namespace std;
vector<int> adj[MAX];
vector<bool> vis(MAX,false);
vi dis(MAX,0);
void dfs(int s,int cnt){
if(vis[s])return;
vis[s]=true;
dis[s]=cnt;
for(auto v:adj[s]){
if(!vis[v]){
dfs(v,cnt+1);
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
int tc=1;
cin>>tc;
For(ti,tc){
int n,k;
cin>>n>>k;
For(i,n){
int u,v;
cin>>u>>v;
adj[u].pb(v);adj[v].pb(u);
}
dfs(1,0);
int mx = INT_MIN,ele;
For(i,MAX){
if(dis[i]>mx){
mx=dis[i];
ele = i;
}
}
For(i,MAX){
vis[i]=false;
dis[i]=0;
}
dfs(ele,0);
mx = INT_MIN;
For(i,MAX){
mx = max(dis[i],mx);
}
if(mx>k){
cout<<mx-k<<endl;
}
else{
cout<<0<<endl;
}
}
}