Cow at Large[USACO 2018 January Platinum]

发表于 分类于 ，

题目链接

loj

题意

假设先固定根节点。如果根节点是一个叶节点，显然答案为 $1$。因此下面考虑的是根节点的度数不为 $1$ 的情况。

显然根节点的最优策略为一直往某个叶子结点走。

假设某个叶节点上有农民，就说明，这条路径一定不能经过这个叶节点到根路径的中点。

那么就会有一个贪心的策略，每次选一个离根节点最近的叶子结点，然后在中点处做个标记，且这个中点的子树中所有的叶节点都不能选了。最后的答案就是标记点的个数。

这样我们就得到了一个 $O(n^2)$ 做法。

下面来看看那些到根的路径中有标记点的点满足什么性质。记 $f_i$ 表示离点 $i$ 最近的叶节点，那么当且仅当 $f_i\leq dep_i$ 时，点 $i$ 在某个标记点的子树中。

但是我们统计的是标记点的个数啊。考虑是否可以转换成跟标记点子树中的点有关的东西。

可以发现，这些标记点不会存在祖先关系。也就是说，一棵子树的贡献是 $1$。

但是怎么在不知道这个树是什么样的情况下，给节点定点权，使得所有点的权值加起来为 $1$ 呢？

考虑度数 $d_i$，当一棵树有 $x$ 个点的时候，$\sum d_i=2x-2$，这个树的根节点会多统计一条，也就是说，子树中是：$\sum d_i=2x-1$，即：$\sum(2-d_i)=1$。

这个做法也太清奇了。。。

那么现在就变成，每个点的点权 $a_i$ 为 $2-d_i$，对于每个节点 $x$，计算 $\sum_{f_y\leq dis_{x,y}}a_i$ 的和。

剩下的就很简单了。点分治，然后做个前缀和，对于每个子树点的贡献减去即可。

时间复杂度 $O(n\log n)$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl;
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
const int N=70005;
const int inf=1e9;
int n;
int ver[N<<1],ne[N<<1],head[N],tot=1;
int d[N],ans[N],f[N];
int siz[N],mx[N],dep[N],rt;
bool vis[N];
inline void add(int x,int y)
{
	ver[++tot]=y; ne[tot]=head[x]; head[x]=tot;
	ver[++tot]=x; ne[tot]=head[y]; head[y]=tot;
	d[x]++; d[y]++;
}
void getroot(int u,int pre,int s)
{
	siz[u]=1; mx[u]=0;
	for(int i=head[u],v;i;i=ne[i])
		if((v=ver[i])!=pre&&!vis[ver[i]])
		{
			getroot(v,u,s);
			siz[u]+=siz[v];
			mx[u]=max(mx[u],siz[v]);
		}
	mx[u]=max(mx[u],s-siz[u]);
	if(mx[rt]>mx[u]) rt=u;
}
int sum[N],st[N],top;
void dfs(int u,int pre)
{
	st[++top]=u;
	for(int i=head[u],v;i;i=ne[i])
		if((v=ver[i])!=pre&&!vis[ver[i]])
		{
			dep[v]=dep[u]+1;
			dfs(v,u);
		}
}
inline void calc(int s,int opt)
{
	fo(i,1,top) sum[min(max(0,f[st[i]]-dep[st[i]]),s+1)]+=d[st[i]];
	fo(i,1,s) sum[i]+=sum[i-1];
	fo(i,1,top) ans[st[i]]+=opt*sum[dep[st[i]]];
	fo(i,0,s+1) sum[i]=0;
}
void divide(int u,int s)
{
	top=0; dep[u]=0; dfs(u,0); calc(s,1);
	vis[u]=1;
	for(int i=head[u],v,Siz;i;i=ne[i])
		if(!vis[v=ver[i]])
		{
			Siz=siz[v]>siz[u]?s-siz[u]:siz[v];
			top=0; dep[v]=1; dfs(v,u); calc(Siz,-1);
		}
	for(int i=head[u],v,Siz;i;i=ne[i])
		if(!vis[v=ver[i]])
		{
			Siz=siz[v]>siz[u]?s-siz[u]:siz[v];
			rt=0; getroot(v,0,Siz); divide(rt,Siz);
		}
}
queue<int> q;
inline void bfs()
{
	fo(i,1,n) if(d[i]==1) q.push(i),f[i]=0,vis[i]=1;
	for(int u;!q.empty();)
	{
		u=q.front(); q.pop();
		for(int i=head[u],v;i;i=ne[i])
			if(!vis[v=ver[i]])
			{
				f[v]=f[u]+1;
				vis[v]=1;
				q.push(v);
			}
	}
	fo(i,1,n) vis[i]=0;
}
int main()
{
	n=read(); mx[0]=inf;
	fo(i,2,n) add(read(),read());
	bfs();
	fo(i,1,n) d[i]=2-d[i];
	rt=0; getroot(1,0,n); divide(rt,n);
	fo(i,1,n) if(d[i]==1) ans[i]=1;
	fo(i,1,n) printf("%d\n",ans[i]);
	return 0;
}