JZOJ5944. 【NOIP2018模拟11.01】信标

数据范围

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

题解

考虑如何放标记是合法的，
很显然，对手在信标两两间的路径的并集的点，一定是不会重复的，
因为两点之间的路径是唯一的。
而对于不在这个集合里面的点，
显然是从集合里面的点为一个端点而引出的一条链，而且一个集合里面的点只能引出一条链。
于是就有了一种贪心思路，
如果一个节点，它往下是链，那么它的答案就是1，
否则，这个点的答案就是所有儿子的答案的和，如果存在一条链，可以忽略掉。
至于哪一个点为根，
可以发现度数大于2的点都是可以的。

code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int N=1000003;
char ch;
void read(int& n)
{
	for(ch=getchar();ch<'0' || ch>'9';ch=getchar());
	for(n=0;'0'<=ch && ch<='9';ch=getchar())n=(n<<1)+(n<<3)+ch-48;
}
int n,nxt[N*2],to[N*2],lst[N];
int x,y,ans,tot,f[N],son[N],d[N];
bool is[N];

void ins(int x,int y)
{
	nxt[++tot]=lst[x];
	to[tot]=y;
	lst[x]=tot;
}

void dfs(int x,int fa)
{
	bool p=0;int ss;
	for(int i=lst[x];i;i=nxt[i])
		if(to[i]^fa)
		{
			dfs(to[i],x),son[x]++;
			f[x]=f[x]+f[to[i]];
			if(is[to[i]])p=1;
			ss=to[i];
		}
	if(son[x]==0 || (is[ss] && son[x]==1))is[x]=1;else is[x]=0;
	if(p)f[x]--;
	if(is[x])f[x]=1;
}

int main()
{
	freopen("beacon.in","r",stdin);
	freopen("beacon.out","w",stdout);
	read(n);
	for(int i=1;i<n;i++)
		read(x),read(y),ins(x,y),ins(y,x),d[x]++,d[y]++;
	ans=1;
	for(int i=1;i<=n;i++)
		if(d[i]>2)
		{
			dfs(i,0);
			ans=f[i];
			break;
		}
	if(n==1)ans=0;
	printf("%d\n",ans);
}