# 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;
}
}
}
```