Submission #2474731

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;
int n,k,num[maxn],need[maxn];
int dp[maxn][2][3],m1[maxn],m2[maxn];
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 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 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];
		int g = num[t]>=k?1:0;
		if(t==u) continue;
		ans = max(ans,dfs2(t,v));
		int add = (m1[v]==(dp[t][1][0]-g))?m2[v]:m1[v];
		ans = max(ans,dp[t][1][1]+need[v]-g+f+add);
	}
	return ans;
}

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

void dfs4(int v,int u){
    m1[v] = m2[v] = 0;
	for(int i=0;i<tree[v].size();i++){
		int t = tree[v][i];
		if(t==u) continue;
		int g = num[t]>=k?1:0;
		if((dp[t][1][0]-g)>=m1[v]){
			m2[v] = m1[v];
			m1[v] = (dp[t][1][0]-g);
		}
		else{
			if((dp[t][1][0]-g)>m2[v]){
				m2[v] = (dp[t][1][0]-g);
			}
		}
		dfs3(t,v);
	}
}

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); 
		dfs4(1,0);
	    cout<<dfs2(1,0)<<endl;
	    for(int i=1;i<=n;i++) tree[i].clear(); 
	}
  return 0;
}

Submission Info

Judge Result