Description：

给一棵树，要求放置最少的信标使得每个点到信标的距离序列不同。

$1\leqslant n\leqslant 10^6$

Solution：

一个重要的性质，如果一个点有 $k$ 棵子树，那么一定至少 $k-1$ 棵子树里放了信标，因为如果有两棵子树都没放信标的话，那么这两棵子树中深度相等的点到所有其他信标的距离都是相同的，肯定没法区分。

然后就直接说结论了，如果树是一条链，那么答案是 $1$ ，否则选出一个度数 $\geqslant 3$ 的点作为根，根不放，子树按上述结论贪心即可。

证明一下，如果有两个点深度相同，那么找到他们的 $LCA$ ，他们一定在 $LCA$ 的两棵子树中，那么一定有至少其中一个子树里放了信标，那么这个一定可以把两个区分出来。如果深度不同，如果他们在根节点同一棵子树中，那么一定有一个子树外的信标可以把它们区分出来，如果他们在不同子树中，那么再分类讨论，如果只有一个子树内有信标，那么就可以直接区分了，如果两个子树内都有，那么到两个点距离相等的位置只有一个，所以一定可以用另一个把他们区分出来。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n;

#define MAXN 1000010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

int deg[MAXN];

void add(int a,int b)

{

	++deg[a];++deg[b];

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

bool v[MAXN];

int ans = 0;

int dfs(int k)

{

	v[k] = true;

	int sum = 0,cnt = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		sum += dfs(e[i].to);

		++cnt;

	}

	if(cnt == 0)return 0;

	if(sum >= cnt - 1)return (sum ? 1 : 0);

	else

	{

		ans += cnt - 1 - sum;

		return 1;

	}

}

int main()

{

	freopen("beacon.in","r",stdin);

	freopen("beacon.out","w",stdout);

	scanf("%d",&n);

	if(n == 1)

	{

		puts("0");

	}

	else

	{

		for(int i = 1;i < n;++i)add(rd(),rd());

		int rt = 0;

		for(int i = 1;i <= n;++i)

		{

			if(deg[i] >= 3)

			{

				rt = i;

				break;

			}

		}

		if(rt == 0)puts("1");

		else

		{

			dfs(rt);

			cout << ans << endl;

		}

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}