[贪心] UOJ139. 【UER #4】被删除的黑白树

贪心地考虑,每个叶节点的覆盖次数应该是深度最小的叶子的深度。

因为若有空,总能找到一系列点多覆盖整棵树一次。

并且能往下传尽量下传,也就是黑点尽量放下面一些,必须要放的时候才能放。

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
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005,maxe=200005;
int n,ans,c[maxn],dis[maxn];
int fir[maxn],nxt[maxe],son[maxe],tot;
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
void dfs_info(int x,int pre){
dis[x]=1e9;
for(int j=fir[x];j;j=nxt[j])
if(son[j]!=pre){
dfs_info(son[j],x);
dis[x]=min(dis[x],dis[son[j]]+1);
}
if(dis[x]>n) dis[x]=1;
}
bool dfs(int x,int pre,int now){
if(dis[x]==now) ans++, now--;
for(int j=fir[x];j;j=nxt[j])
if(son[j]!=pre) dfs(son[j],x,now);
}
int main(){
freopen("uoj139.in","r",stdin);
freopen("uoj139.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n-1;i++){
int x,y; scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs_info(1,1);
dfs(1,1,dis[1]);
printf("%d\n",ans);
return 0;
}