Submission #2474589

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;
int n,k,s[maxn],num[maxn],need[maxn];
int dp[maxn][2][3];
vector<int> tree[maxn];

int dfs1(int v,int u){
	num[v] = 1;need[v] = 0;
	for(int i=0;i<tree[v].size();i++){
		int t = tree[v][i];
		if(t==u) continue;
		num[v] += dfs1(t,v);
		if(num[t]>=k) need[v]++;			
	}
	return num[v];
}

int dfs2(int v,int u){
    int ans = 0;
    if(n-num[v]>=k&&num[v]>=2) ans = 1;
    int f = (n - num[v])>=k?1:0;
	for(int i=0;i<tree[v].size();i++){
		int t = tree[v][i];
		if(t==u) continue;
		ans = max(ans,dfs2(t,v));
		ans = max(ans,need[t]+s[v]-dp[t][1][0]+f);
	}
	return ans;
}

void dfs3(int v,int u){
    s[v] = 0;
	for(int i=0;i<tree[v].size();i++){
		int t = tree[v][i];
		if(t==u) continue;
		s[v] += dp[t][1][0];
		dfs3(t,v);
	}
}

int dfs(int v,int u){
	dp[v][1][0] = 0;
	if(num[v]>=k) dp[v][1][0] = 1;
	for(int i=0;i<tree[v].size();i++){
		int t = tree[v][i];
		int f = num[t]>=k?1:0;
		if(t==u) continue;
		if(dp[t][1][0]>=0) dp[v][1][0] = max(dp[v][1][0],need[v]+dp[t][1][0]-f);
		else dp[v][1][0] = max(dp[v][1][0],need[v]+dfs(t,v)-f);
	}
	return dp[v][1][0];
}

int main(){
	while(cin>>n>>k){
	    memset(dp,-1,sizeof dp);
	    for(int i=1;i<n;i++){
	    	int x,y;cin>>x>>y;
	    	tree[x].push_back(y);
	    	tree[y].push_back(x);
		}
		dfs1(1,0);	
		dfs(1,0);
		dfs3(1,0); 
	    cout<<dfs2(1,0)<<endl;
	    for(int i=1;i<=n;i++) tree[i].clear(); 
	}
	return 0;
} 

Submission Info

Judge Result