BZOJ 2067: [POI2004]SZN – [二分/树形DP]


题目传送门(BZOJ)
>原文链接<

题解 :

我们把两问分开看

第一问 :

考虑以点x为顶点的线要多少根.

由于有一条线是从父亲来的, 并且还可以继续向下给它的一个儿子, 所以就是其他儿子两两配对需要的线条数

\lceil\frac{\deg[x]-2}{2}\rceil,也就是\lfloor\frac{\deg[x]-1}{2}\rfloor

其中根节点需要特判, 它没有从父亲来的线, 也就是先在答案上加一, 来表示这条线是继承下来的线.

1+\sum\limits_{i=1}^{n}\lfloor\frac{\deg[i]-1}{2}\rfloor

第二问 :

第二问有很鲜明的二分标志 : 最长最短.

我们先二分一个答案mid, 然后考虑如何验证 :

f[i]=f[to]+1, 我们先把i的儿子的f拿过来排个序,

此时我们再二分一下, 假设i从父亲那继承来的点要给点now接下去,

那么删掉now后,其他点贪心的两两配对长度不能超过mid

这样我们在二分出来的可行的前提下贪心的使f[i]尽可能的小, 因为这样会有利于以后的答案.

直接拿那个尽可能小的答案来更新f即可

根节点同样需要特判, 配对删最大的即可

代码 :

#include 
#include 
#include 
#include 
using namespace std;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
char buf[100000], *p1, *p2; 
const int N = 11000;
inline int rd() {
    int x = 0; char ch = nc();
    while(!isdigit(ch)) ch = nc();
    while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc();
    return x;
}
#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)
struct Edge {
    int to;
    Edge *next;
}*h[N], e[N<<1];
inline void addEdge(int u, int v) {
    static int _;
    Edge *tmp = &e[++_]; tmp->to = v; tmp->next = h[u]; h[u] = tmp;
}
int deg[N], f[N], g[N], n, mid;
bool flag;
inline bool check(int x) {
    for(int i = 1, j = *g; i < j; i ++, j -- ) {
        if(i == x) ++ i;
        if(j == x) -- j;
        if(g[i]+g[j] > mid) return 0;
    }
    return 1;
}
void dfs(int p, int fa) {
    rev(i, p) if(i->to != fa) dfs(i->to, p);
    *g = 0;
    rev(i, p) if(i->to != fa) g[++*g] = f[i->to]+1;
    if(p == 1) {
        sort(g+1, *g+g+1);
        flag &= check((*g&1)?*g:0);
        return ;
    }
    if(!(*g&1)) g[++*g] = 0;
    sort(g+1, *g+g+1);
    int l = 1, r = *g+1;
    while(l < r) {
        int now = (l+r) >> 1;
        if(g[now]+1 <= mid && check(now)) r = now;
        else l = now+1;
    }
    flag &= (l!=*g+1);
    f[p] = g[l];
}
int main() {
    n = rd();
    for(int i = 2; i <= n; i ++ ) {
        int u = rd(), v = rd();
        deg[u] ++, deg[v] ++ ;
        addEdge(u, v), 
        addEdge(v, u);
    }
    int ans = 1;
    for(int i = 1; i <= n; i ++ ) ans += (deg[i]-1)>>1;
    printf("%d ", ans);
    int l = 1, r = n;
    while(l < r) {
        mid = (l+r) >> 1; flag = 1;
        dfs(1, 0);
        if(flag) r = mid;
        else l = mid+1;
    }
    printf("%d\n", l);
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注