题目大意
企鹅国的网吧们之间由网线互相连接，形成一棵树的结构。现在由于冬天到了，供暖部门缺少燃料，于是他们决定去拆一些网线来做燃料。但是现在有$K$只企鹅要上网和别人联机游戏，所以他们需要把这$K$只企鹅安排到不同的机房（两只企鹅在同一个机房会吵架），然后拆掉一些网线，但是需要保证每只企鹅至少还能通过留下来的网线和至少另一只企鹅联机游戏。
所以他们想知道，最少需要保留多少根网线？
题目分析
这。。。取暖烧网线。。。
不难发现，若我们尽量选出点不重叠的边，是最优的策略，因为保留一条边就可以满足两个企鹅。
假设已经求出了最多有$tmp$条点不重叠的边，若仍不能满足要求，那么就要在刚刚选出的边上加点，显然加一条边多一个可选企鹅，答案为$tmp+(k-2*tmp)$。
若$tmp$条已经超出了要求，那么随便选几条即可，答案为：$k/2+(k\&1)$。
那么我们将问题转化为了求出最多的点不重叠的边，据说这个叫做最大匹配？
有贪心和动规两种方式求解，这里使用动规求解。
设$f[i,0/1]$表示$i$号点 否/是 与其子结点连边所得到的最多的点不重叠的边。
然后打个标记转移即可。
代码
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
int t,n,k,f[maxn][2];
void TreeDp(int Now,int father) {
f[Now][0]=f[Now][1]=0;
bool bj=0,vst=0;
int Max=-0x7fffffff/2;
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
if(Next==father)continue;
TreeDp(Next,Now);
if(f[Next][0]>=f[Next][1])bj=1;
Max=max(Max,f[Next][0]-f[Next][1]);
f[Now][1]+=max(f[Next][0],f[Next][1]);
f[Now][0]+=max(f[Next][0],f[Next][1]);
vst=1;
}
if(!bj)f[Now][1]+=Max;
f[Now][1]+=vst;
}
int main() {
t=Get_Int();
while(t--) {
n=Get_Int();
for(int i=1; i<=n; i++)edges[i].clear();
k=Get_Int();
for(int i=2; i<=n; i++) {
int x=Get_Int();
AddEdge(i,x);
AddEdge(x,i);
}
TreeDp(1,0);
int tmp=max(f[1][0],f[1][1]);
if(2*tmp<=k)printf("%d\n",tmp+(k-2*tmp));
else printf("%d\n",k/2+k%2);
}
return 0;
}
|
