P2899 [USACO08JAN] Cell Phone Network G (树型dp)

测试链接

题目描述

Farmer John 想让他的所有牛用上手机以便相互交流。他需要建立几座信号塔在

N

N

N 块草地中。已知与信号塔相邻的草地能收到信号。给你

N

−

1

N-1

N−1 个草地

(

A

,

B

)

(A,B)

(A,B) 的相邻关系，问：最少需要建多少个信号塔能实现所有草地都有信号。

输入格式

第

1

1

1 行：一个整数

N

N

N。

第

2

2

2 行到第

N

N

N 行：每一行两个整数，用空格分隔，给出一对相邻的草地

A

A

A 和

B

B

B。

输出格式

一个整数，表示要安装的最少信号塔数。

输入输出样例 #1

输入 #1

5
1 3
5 2
4 3
3 5

输出 #1

2

说明/提示

对于所有的数据，

1

≤

N

≤

10

4

1 \\leq N \\leq 10^4

1≤N≤104，

1

≤

A

,

B

≤

N

1 \\leq A,B \\leq N

1≤A,B≤N，

A

≠

B

A \\neq B

A=B。

思路

与leedcode968 监控二叉树的思路类似，贪心+树型dp，分类讨论

题解

#include <bits/stdc++.h>
const int N = 1e4+10;
using namespace std;
vector<int>graph[N];
int ans=0;
int n;

int f(int u,int p)
{
bool s0= false;
bool s2 = false;
for(auto v:graph[u])
{
if(v==p)continue;
int cs = f(v,u);
if(cs==2)s2 = true;
else if(cs==0)s0=true;
}
if(s0)
{
ans++;
return 2;
}
if(s2)
{
return 1;
}
return 0;
}

int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
int f,t;
cin>>f>>t;
graph[f].push_back(t);
graph[t].push_back(f);
}
if(n==1)
{
cout<<1<<endl;
return 0;
}
if(f(1,0)==0)ans++;
cout<<ans<<endl;

return 0;
}