Submission #2106101

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
#define pq priority_queue
#define P pair<int,int>
#define P2 pair<int,P>
#define P3 pair<int,P2>
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};
const ll LINF=1e18;
const ld PI=abs(acos(-1));

int n,k;
int min_cost[2010];
vector<int> g[2010];

void solve(int s, int t, int min_cost[2010]){
	REP(i,0,n) min_cost[i] = INF; min_cost[s] = 0; min_cost[t] = 0;
	queue<P> qu; qu.push({0, s}); qu.push({0, t});
	
	while(!qu.empty()){
		auto p = qu.front(); qu.pop();
		
		for(auto e:g[p.second]){
			if(p.first + 1 >= min_cost[e]) continue;
			min_cost[e] = p.first + 1;
			qu.push({min_cost[e], e});
		}
	}
}

int main(){
	cin >> n >> k;
	REP(i,0,n - 1){
		int a,b; cin >> a >> b;
		g[a - 1].push_back(b - 1);
		g[b - 1].push_back(a - 1);
	}
	
	int mi = INF;
	if(k%2){
		REP(i,0,n){
			for(auto e:g[i]){
				int c = 0;
				solve(i, e, min_cost);
				REP(i,0,n) if(min_cost[i] > (k - 1) / 2) c++;
				mi = min(mi, c);
			}
		}
	}else{
		REP(i,0,n){
			int c = 0;
			solve(i, i, min_cost);
			REP(i,0,n) if(min_cost[i] > k / 2) c++;
			mi = min(mi, c);
		}
	}
	
	cout << mi << endl;
	return 0;
}

Submission Info

Judge Result