【JZOJ A组】信标

Description

【JZOJ A组】信标

Input

第一行一个正整数 n.
接下来 n − 1 行每行两个个正整数 u, v, 表示有一条连接 u, v 的道路.

Output

一行, 表示最少需要的信标数量.

Sample Input

4
1 2
1 3
1 4

Sample Output

样例 1 解释
在村庄 3, 4 放置信标, 四个村庄接收到的定位序列分别为 [1, 1], [2, 2], [0, 2], [2, 0].
如果只在 3 放置, 则村庄 2, 4 接收到的定位序列都是 [2], 不满足要求.
注意定位序列是有序的.

Data Constraint

样例 2
见下发文件中的 ex_beacon2.in/out.

Hint

对于前 20% 的数据, n ≤ 10;
对于前 45% 的数据, n ≤ 40, 树的形态随机;
对于前 70% 的数据, n ≤ 5000;
对于另 5% 的数据, 不存在一个村庄连接着 3 条或以上的道路;
对于 100% 的数据, 1 ≤ n ≤ 1000000, 1 ≤ u, v ≤ n, 保证数据合法.

思路

由于在 n > 1 时答案至少为 1, 我们枚举一个必须放的根, 所有深度不同的点就被区分开了.
设一个节点有 c 个儿子, 发现必须在其中至少 c − 1 个儿子的子树中放置信标. 证明如下:
考虑如果不这样放, 对于两棵都没有放的子树, 他们汇集到 lca 上以后距离都是相等的, 所以 lca外的信标无法区分, 而内部没有信标. 所以不能存在两颗子树都不放. 所以至少要放 c − 1 个.
由于在根节点放置了信标, 可以只考虑深度相同的点. 由于深度相同, 所以他们的 lca 度数至少为 2, 那么一定有一个信标在 lca 包含这两个点的两支子树中. 那么另一侧的点肯定要走更远的路,会被区分开. 所以放 c − 1 个足够区分.
这样问题变成每个节点要有 c − 1 棵子树放有信标, 求最小方案. 直接贪心即可. 由于枚举根所以复杂度为 O(n²), 可以获得 70 分.

如何做到 O(n)? 我们先特判链的情况答案为 1, 然后找到任意一个度数大于 2 的节点, 可以证明这个点一定不需要放置信标. 于是以这个点作根 O(n) 的贪心即可. 证明如下：
深度相同的点对证明同上, 只考虑深度不同的点对. 如果它们在一颗子树中, 由于度数大于 2 所以一定有另一颗子树的一个信标把他们区分开. 如果在不同的子树中, 有两种情况：
一个在没放信标的子树中, 一个在放了的子树中. 显然还存在另一个子树放了信标, 由于深度不同他们会被这个信标区分开.
两个都在放了信标的子树中. 如果根的度数大于 3 则同上. 度数等于 3 时, 如果他们没有被区分开, 一定是他们先汇集到了一个节点上, 然后走到同一个信标上. 这个点一定是一条奇链的中点, 且不是根 (由于深度不同), 是在两个子树之一中唯一的. 那么他们走到另一个信标就一定有一个点走了冤枉路, 既另一个信标可以区分出他们.

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000077;
int n,list[maxn],d[maxn],a[maxn],cnt,rt;
struct E
{
	int to,next;
}e[maxn*2];
void add(int u,int v)
{
	e[++cnt].to=v; e[cnt].next=list[u]; list[u]=cnt;
}
void dfs(int u,int fa)
{
	int s=0;
	for(int i=list[u]; i; i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u);
		a[u]+=a[v];
		if(!a[v]) s++;
	}
	if(s) a[u]+=s-1;
}
int main()
{
	freopen("beacon.in","r",stdin);
	freopen("beacon.out","w",stdout);
	scanf("%d",&n);
	if(n==1)
	{
		printf("0"); return 0;
	}
	for(int i=1,x,y; i<n; i++) scanf("%d%d",&x,&y),add(x,y),add(y,x),d[x]++,d[y]++;
	for(int i=1; i<=n; i++) if(d[i]>2)
	{
		rt=i; break;
	}
	if(!rt)
	{
		printf("1"); return 0;
	}
	dfs(rt,0);
	printf("%d",a[rt]);
}