Submission #808235

---

Source Code Expand

#include <bits/stdc++.h>
#define MAXN 2005
#define MYINF 1000000000

using namespace std;

static int dp[MAXN][MAXN];

static int a[2*MAXN];
static int s[MAXN];
static int mins[MAXN][MAXN];

int N, K;
int res;

void DFS (int point, int par)
{
	dp[point][0] = 1;
	int i, j;
	for (i = s[point]; i < s[point+1]; i++)
	{
		if (a[i] != par)
		{
			DFS(a[i], point);
			dp[point][0] += dp[a[i]][0];
			mins[a[i]][0] = dp[a[i]][0];
			for (j = 1; j <= K+1; j++)
			{
				mins[a[i]][j] = min(mins[a[i]][j-1], dp[a[i]][j]);
			}
		}
	}
	dp[point][1] = dp[point][0] - 1;
	for (j = K+1; j > 1; j--)
	{
		int minSum = 0;
		for (i = s[point]; i < s[point+1]; i++)
		{
			if (a[i] != par)
			{
				minSum += mins[a[i]][min(K-j+1, j-1)];
			}
		}
		dp[point][j] = MYINF;
		for (i = s[point]; i < s[point+1]; i++)
		{
			if (a[i] != par)
			{
				int temp = dp[a[i]][j-1] + minSum - mins[a[i]][min(K-j+1, j-1)];
				dp[point][j] = min(dp[point][j], temp);
			}
		}
	}
	for (j = 0; j <= K+1; j++)
	{
		res = min(res, dp[point][j] + (N - dp[point][0]));
	}
}

int main ()
{
	static pair<int, int> data[MAXN];
	scanf("%d %d",&N,&K);
	int M = N-1;
	int i;
	memset(s, 0, sizeof(s));
	for (i = 0; i < M; i++)
	{
		scanf("%d %d",&data[i].first,&data[i].second);
		data[i].first--;
		data[i].second--;
		s[data[i].first]++;
		s[data[i].second]++;
	}
	for (i = 1; i <= N; i++) s[i] += s[i-1];
	for (i = 0; i < M; i++)
	{
		s[data[i].first]--;
		a[s[data[i].first]] = data[i].second;
		s[data[i].second]--;
		a[s[data[i].second]] = data[i].first;
	}
	res = N;

	DFS(0, -1);
	printf("%d\n",res);

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:63:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&K);
                      ^
./Main.cpp:69:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&data[i].first,&data[i].second);
                                                ^

Judge Result