题目描述
Treeland 有 $n$ 个城市,标号从 $0…n-1$。有 $n-1$ 条双向道路连接了 $n$ 个城市构成一颗树。 Treeland 的居民想要建造一套 TPS 系统 (Treeland Positioning System)。TPS 是一个能帮助人定位他在哪个城市的系统。系统由 $k$ 个信标构成，每个信标被安放在一个城市。当一个人打开他的 TPS 接收器的时候他能得到他与每一个信标的距离 (这里距离指树上两点之间经过的边的数量) 。 显然只有当在不同的城市打开 TPS 接收器接受到的信息不一样的时候 TPS 系统才能正常工作。（也就不存在两个不同的城市使得在他们那里接收到的信号相同）注意不同的信标之间是可以区分的。求最少安放多少信标才能使 TPS 系统正常工作。
约定与限制
- $n\in [1,50]$
- 时间限制: $2$ s
- 空间限制: $64$ MB
思路
我们先假定选择了一个点为根，并且在根节点放置了信标。
设一个节点有 $c$ 个儿子，发现必须在其中至少 $c − 1$ 个儿子的子树中放置信标。证明如下：
- 考虑如果不这样放，对于两棵都没有放的子树，他们汇集到 $lca$ 上以后距离都是相等的，所以 $lca$ 外的信标无法区分，而内部没有信标。所以不能存在两颗子树都不放，至少要放 $c − 1$ 个；
-
由于在根节点放置了信标，可以只考虑深度相同的点。因为他们的 $lca$ 度数至少为 2，那么一定有一个信标在 $lca$ 包含这两个点的两支子树中。那么另一侧的点肯定要走更远的路，会被区分开。所以放 $c − 1$ 个足够区分。
所以，对于一个确定的根，我们可以贪心地放置信标，得到当前的答案。
如何选择这个根呢？找到任意一个度数大于 2 的节点，可以证明实际上这个点一定不需要放置信标，以这个点作根 $\Theta(n)$ 的贪心即可。证明如下：
对于深度相同的点，显然两个信标就可以区分它们，现在只考虑深度不同的点对。如果它们在一颗子树中，由于度数大于 2 所以一定有另一颗子树的一个信标把他们区分开。如果在不同的子树中，有两种情况：
- 一个在没放信标的子树中，一个在放了的子树中。显然还存在另一个子树放了信标，由于深度不同他们会被这个信标区分开。
-
两个都在放了信标的子树中。如果根的度数大于 3 则另一个子树的信标会区分它们同上。度数等于 3 时，如果他们没有被区分开，一定是他们先汇集到了一个节点，然后走到同一个信标上。这个点一定是一条奇链的中点，且不是根 (由于深度不同)，是在两个子树之一中唯一的。那么他们走到另一个信标就一定有一个点走了更远的路，既另一个信标可以区分出他们。
所以最后的时间复杂度 $\Theta(n)$。
代码
#include <bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define maxn 1000100
struct ios{
inline char read(){
static const int IN_LEN=1<<18|1;
static char buf[IN_LEN],*s,*t;
return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
}
template <typename _Tp> inline ios & operator >> (_Tp&x){
static char c11,boo;
for(c11=read(),boo=0;!isdigit(c11);c11=read()){
if(c11==-1)return *this;
boo|=c11=='-';
}
for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
boo&&(x=-x);
return *this;
}
}io;
struct Edge{
int to,next;
Edge(int a=0,int b=0){
to=a,next=b;
}
}l[maxn<<1];
int head[maxn],cnt,n,root;
int f[maxn],deg[maxn];
void Add(int a,int b){
l[++cnt]=Edge(b,head[a]);
head[a]=cnt;
}
void Dfs(int u,int fa){
bool flag=0;
for (register int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v==fa) continue;
Dfs(v,u);
f[u]+=max(1,f[v]);
if (!f[v]) flag=1;
}
f[u]-=flag;
}
int main(){
freopen("beacon.in","r",stdin);
freopen("beacon.out","w",stdout);
io>>n;
if (n==1){puts("0");return 0;}
for (register int i=1,a,b;i<n;++i){
io>>a>>b;
Add(a,b),Add(b,a);
deg[a]++,deg[b]++;
}
for (register int i=1;i<=n;++i)
if (deg[i]>2) {root=i;break;}
if (!root){puts("1");return 0;}
Dfs(root,0);
printf("%d",f[root]);
}