PATHCHEF-Editorial

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:-

  1. Pick any vertex as a source vertex.
  2. 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.
  3. Pick the vertex with maximum distance, and repeat step 2.
  4. 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;
        }
	}
}