Toll Roads

#include <bits/stdc++.h>

#define i64 long long
#define u64 unsigned long long
#define i32 int
#define u32 unsigned int

#define pii pair<int, int>
#define pll pair<long long, long long>

#define ld long double
#define defmod 1000000007

#define mati64(a,b) vector<vector<i64>>(a, vector<i64>(b, 0));
using namespace std;

int n, k;
vector<int> v[5050];
int pa[5050];
vector<pair<int, int>> al[5050];
int de[5050];

void hae1(int cur){
  for(auto f: v[cur]){
    if(f == pa[cur])
      continue;
    pa[f] = cur;
    hae1(f);
    al[cur].push_back({de[f]+1, f});
    de[cur] = max(de[f]+1, de[cur]);
  }
}
vector<bool> d1;
multiset<int> cc;
int gp(int cur, int last){
  if(al[cur][0].second == last){
    if(al[cur].size() == 1)
      return -1;
    return al[cur][1].first;
  }
  return al[cur][0].first;
}
pair<int, int> gp2(int cur, int last, int last2){
  if(al[cur][0].second == last || al[cur][0].second == last2){
    if(al[cur].size() == 1)
      return {0, -1};
    if(al[cur][1].second == last || al[cur][1].second == last2){
      if(al[cur].size() == 2)
	return {0, -1};
      return al[cur][2];
    }
    return al[cur][1];
  }
  return al[cur][0];
}
pair<int, int> gp3(int cur, int last, int last2, int last3){
  if(al[cur][0].second == last || al[cur][0].second == last2 || al[cur][0].second == last3){
    if(al[cur].size() == 1)
      return {0, -1};
    if(al[cur][1].second == last || al[cur][1].second == last2|| al[cur][0].second == last3){
      if(al[cur].size() == 2)
	return {0, -1};
      if(al[cur][2].second == last || al[cur][2].second == last2|| al[cur][2].second == last3){
          if(al[cur].size() == 3)
	    return {0, -1};
	  return al[cur][3];
      }
      return al[cur][2];
    }
    return al[cur][1];
  }
  return al[cur][0];
}
void adpis(int cur){
  for(auto f: v[cur]){
    if(f == pa[cur])
      continue;
    al[f].push_back({gp(cur, f)+1, cur});
    sort(al[f].begin(), al[f].end(), greater<pair<int, int>>());
    adpis(f);
  }
}
int ans = 10000, at = 10000, aa, ab;
int alk = 0;
void hae2(int cur, int last, int d){
  //cout << "cur " << cur << " last " << last << " d " << d << endl;
  if(d > k)
    return;
  if(d != 0){
    pii fak = gp2(cur, last, -1);
    cc.insert(fak.first);
    pii fakw = gp2(cur, last, fak.second);
    cc.insert(fakw.first);
    int be = 10000;
    if(cc.size() == 1){
      //cout << "be " << *cc.rbegin() << endl;
      be = *cc.rbegin();
    }
    else{
      be = *cc.rbegin();
      cc.erase(cc.find(be));
      int vv = *cc.rbegin();
      cc.insert(be);
      be+=vv;;
    }
    if(be < ans){
      
      ans = be;
      at = d;
      aa = alk;
      ab = cur;
      //cout << "taalla1 " << aa << " " << ab << " " << d<< endl;
    }
    else if(be == ans && d < at){
      ans = be;
      at = d;
      aa = alk;
      ab = cur;
      //cout << "taalla " << aa << " " << ab << " " << d<< endl;
    }
    //cout << alk << "->"<< cur << " mukana " << endl;
    //for(auto f: cc)
    //  cout << f << " ";
    //cout << endl << endl;
    cc.erase(cc.find(fak.first));
    cc.erase(cc.find(fakw.first));
  }
  
  for(auto f: v[cur]){
    if(f == last)
      continue;
    pair<int, int> lis = gp2(cur, last, f);
    cc.insert(lis.first);
    pair<int, int> lis2 = gp3(cur, last, f, lis.second);
    cc.insert(lis2.first);
    hae2(f, cur, d+1);
    cc.erase(cc.find(lis.first));
    cc.erase(cc.find(lis2.first));
  }
  
}
int main(){
  cin.sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for(int i = 0; i < n-1; ++i){
    int a, b; cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  hae1(0);
  for(int i = 0; i < n; ++i){
    sort(al[i].begin(), al[i].end(), greater<pair<int, int>>());
  }
  adpis(0);

  for(int i = 0; i < n; ++i){
    cc.clear();
    
    int be = 0;
    //cout << i << ": ";
    //for(auto f: al[i])
    //  cout << f.first << "," << f.second << " ";
    //cout << endl;
    if(al[i].size() == 1)
      be = al[i][0].first;
    else if(al[i].size() > 1)
      be = al[i][0].first+al[i][1].first;
    if(be < ans){
      ans = be;
      at = 0;
      aa = i;
      ab = i;
    }
    alk = i;
    hae2(i, -1, 0);
  }
  if(at == 0)
    cout << ans << endl << at << endl;
  else
    cout << ans << endl << at << endl << aa << " " << ab << endl;
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: ACCEPTED

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: ACCEPTED

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: WRONG ANSWER

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: ACCEPTED

Test 28

Verdict: WRONG ANSWER

Test 29

Verdict: WRONG ANSWER

Test 30

Verdict: WRONG ANSWER

Test 31

Verdict: WRONG ANSWER

Test 32

Verdict: WRONG ANSWER

Test 33

Verdict: WRONG ANSWER

Test 34

Verdict: WRONG ANSWER

Test 35

Verdict: TIME LIMIT EXCEEDED

Test 36

Verdict: TIME LIMIT EXCEEDED

Test 37

Verdict: TIME LIMIT EXCEEDED

Test 38

Verdict: TIME LIMIT EXCEEDED

Test 39

Verdict: TIME LIMIT EXCEEDED

Test 40

Verdict: TIME LIMIT EXCEEDED

Test 41

Verdict: WRONG ANSWER

Test 42

Verdict: WRONG ANSWER

Test 43

Verdict: WRONG ANSWER

Test 44

Verdict: WRONG ANSWER

Test 45

Verdict: WRONG ANSWER

Test 46

Verdict: WRONG ANSWER

Test 47

Verdict: WRONG ANSWER

Test 48

Verdict: WRONG ANSWER

Test 49

Verdict: TIME LIMIT EXCEEDED

Test 50

Verdict: TIME LIMIT EXCEEDED

Test 51

Verdict: TIME LIMIT EXCEEDED

Test 52

Verdict: TIME LIMIT EXCEEDED

Test 53

Verdict: TIME LIMIT EXCEEDED

Test 54

Verdict: WRONG ANSWER

Test 55

Verdict: WRONG ANSWER

Test 56

Verdict: WRONG ANSWER

Test 57

Verdict: WRONG ANSWER

Test 58

Verdict: WRONG ANSWER

Test 59

Verdict: WRONG ANSWER

Test 60

Verdict: TIME LIMIT EXCEEDED

Test 61

Verdict: TIME LIMIT EXCEEDED

Test 62

Verdict: TIME LIMIT EXCEEDED

Test 63

Verdict: TIME LIMIT EXCEEDED

Test 64

Verdict: TIME LIMIT EXCEEDED

Test 65

Verdict: TIME LIMIT EXCEEDED

Test 66

Verdict: TIME LIMIT EXCEEDED

Test 67

Verdict: TIME LIMIT EXCEEDED

Test 68

Verdict: ACCEPTED

Test 69

Verdict: WRONG ANSWER

Test 70

Verdict: ACCEPTED

Test 71

Verdict: WRONG ANSWER

Test 72

Verdict: WRONG ANSWER