1、http://poj.org/problem?id=3107 2、题目大意; 有n个点，已知他们之间的关系，连接是双向的，求删除哪个点可以使得剩下的各个部分的点的个数最少 用一个cnt[]数组记录下每个点有多少个子节点 那么我们要求的删除根节点u后剩余部分的最大数就是要么是u的子树中的最大值，要么是除去以u为根的树外的剩余结点数dp[u]=max(max(cnt[v]),n-cnt[u

网上的写法都是dp，然后发现一个构造写法，太稳了ORZ http://blog.csdn.net/PoPoQQQ/article/details/48006557 具体的证明可以看这个博客，我这里就只写构造方法了。 首先答案只和a、b、c二进制中1的数量有关，不妨设为x、y、z且x>=y。 分成三种情况（几种特殊情况也能包括进去）： 1<=z<=y 0–0000–11111111