Submission #808378

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
#define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
#define rep(i, c) for(auto &(i) : (c))
#define x first
#define y second
#define pb push_back
#define PB pop_back()
#define iOS ios_base::sync_with_stdio(false)
#define sqr(a) (((a) * (a)))
#define all(a) a.begin() , a.end()
#define error(x) cerr << #x << " = " << (x) <<endl
#define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
#define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
#define coud(a,b) cout<<fixed << setprecision((b)) << (a)
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define umap unordered_map
#define double long double
typedef long long ll;
typedef pair<int,int>pii;
typedef vector<int> vi;
typedef complex<double> point;
template <typename T> using os =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>  inline void smax(T &x,T y){ x = max((x), (y));}
template <class T>  inline void smin(T &x,T y){ x = min((x), (y));}
const int maxn = 2100;
vi adj[maxn];
int cnt = 0, ans = 0;
int dp[maxn][maxn], sz[maxn], odp[maxn][maxn];
int n, k;
inline void dfs(int v = 0, int p = -1){
	sz[v] = 1;
	For(i,0,n+1)	smax(dp[v][i], 1);
	rep(u, adj[v])	if(u - p){
		dfs(u, v);
		For(i,0,sz[v] + 1)	odp[v][i] = dp[v][i];
		rof(i,sz[v],-1)
			For(j,0,sz[u]+1)if(i + j + 1 <= k)
				smax(dp[v][max(i, j+1)], odp[v][i] + dp[u][j]);
		sz[v] += sz[u];
	}
	For(i,1,n+1)	smax(dp[v][i], dp[v][i-1]);
}
int main(){
	iOS;
	cin >> n >> k;
	For(i,1,n){
		int v, u;
		cin >> v >> u;
		-- v, -- u;
		adj[v].pb(u), adj[u].pb(v);
	}
	dfs(0);
	For(i,0,n)	smax(ans, dp[i][k]);
	cout << n-ans << endl;
	return 0;
}

Submission Info

Judge Result