UOJ 139 【UER #4】被删除的黑白树
简要题意：将一棵树上的一些节点染成黑色，使每个叶子节点到根节点的黑色节点数和相等。最大化黑色节点数。
Task1: 30pts $n\le 20$
Task2: 30pts $n\le 1000$
Task3: 40pts $n\le 100000$
错误想法1
首先我们发现树根是一定要染成黑色的。
接下来我们发现好像可以递归下去。
之后我们发现每个点到根的黑色节点数大最可以是深度最小的叶子节点的深度。
然后似乎答案就是深度不超过深度最小的叶子节点的深度的点数？
显然可以过小样例。
然后一交，GG！Task1的第一个测试点就挂了。
然后非常懵逼并且不知道发生什么的时候，突然发现：居然还有大样例？？？
然后下下来大样例一看，炸飞了。
答案比标准答案小了很多。
在经过很久的XJB调试之后，我终于发现了问题，并想到了错误算法二。
错误算法二
我们发现，在这棵树中，这个算法是明显错误的：
很显然，每个点到根的距离是2，在错误算法1中会染黑1,2,3,4但是明显1,2,3,5,6更优。
然后我们直观的想，貌似可以从浅到深的顺序对每个点染到它的k级祖先。
显然如果直接染的话，并不能过什么数据，会比标答大很多。
如果通过维护到根路径上已经染的个数，先不管会不会WA，反正肯定会T飞。
正确算法
显然
每个点到根的黑色节点数是深度最小的叶子节点的深度
这个条件是一定满足的。如果不满足则一定不是最大答案。
所以根据这一点，我们想到了正确的算法：
对根开始判断：
对于以某一个点为根的子树，如果这个点不染黑则满足不了条件则不染。否则就染。
然后递归到子树计算。
正确性显然。
代码
/*
Author: CNYALI_LK
LANG: C++
PROG: 139.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int dis[102424];
int dmn[102424],son[102424];
int beg[102424],to[204848],lst[204848],e;
void add(int u,int v){
to[++e]=v;
lst[e]=beg[u];
beg[u]=e;
}
int f[102424],cnt;
int ys[102424];
void dfs(int x,int fa){
dis[x]=dis[fa]+1;
// ++dcnt[dis[ys[x]]];
son[x]=0;
dmn[x]=0x3f3f3f3f;
for(int i=beg[x];i;i=lst[i])if(to[i]!=fa){
son[x]=1;
dfs(to[i],x);
chkmin(dmn[x],dmn[to[i]]+1);
}
if(dmn[x]==0x3f3f3f3f)dmn[x]=1;
}
int a[102424];
int discmp(int x,int y){
return dis[x]<dis[y];
}
int dfs1(int x,int cnt,int fa){
int ans=0;
if(dmn[x]==cnt){
--cnt;
++ans;
}
for(int i=beg[x];i;i=lst[i])if(to[i]!=fa){
ans+=dfs1(to[i],cnt,x);
}
return ans;
}
int main(){
#ifdef cnyali_lk
freopen("139.in","r",stdin);
freopen("139.out","w",stdout);
#endif
int n,u,v,ans=0;
scanf("%d",&n);
for(int i=1;i<n;++i){
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs(1,0);
int as=dmn[1],t=0;
printf("%d\n",dfs1(1,dmn[1],0));
return 0;
}