NKOJ 4038 (CQOI 2017) 小Q的棋盘（贪心）

发表于 |
字数统计: 260字 | 阅读时长 ≈ 1min

NKOJ4038

考虑到是一颗树，所以先找出从0号点出发的最长链，假设长度为L。
如果L>=N，那么答案就是N+1
如果L<N，此时肯定发生了某些点走两次的情况，那么最优解就是在一些链上走2次，最后在最长链上走到底，这是显然的。因此答案是（N-L）/2+L+1

附上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 12345
using namespace std;
int v,n,l;
int LA[N],NE[N],EN[N],TOT;
void ADD(int x,int y)
{
	TOT++;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void DFS(int x,int f,int d)
{
	l=max(l,d);
	for(int i=LA[x];i;i=NE[i])
	if(EN[i]!=f)DFS(EN[i],x,d+1);
}
int main()
{
	int i,x,y;
	scanf("%d%d",&v,&n);
	for(i=1;i<v;i++)
	{
		scanf("%d%d",&x,&y);
		ADD(x,y);ADD(y,x);
	}
	DFS(0,-1,0);
	if(l>=n)cout<<n+1;
	else cout<<min((n-l)/2+l+1,v);
}