$bzoj2067 szn$ 二分+贪心

正解:二分+贪心

解题报告:

题目大意就说有一棵树,然后要用若干条线覆盖所有边且不能重叠.问最少要用几条线,在用线最少的前提下最长的线最短是多长.

昂首先最少用多少条线这个还是蛮$easy$的$QwQ$?显然答案就$1+sum frac{d_i-1}{2}$.考虑每个点的儿子都两两匹配,多出来的部分直接到父亲处做就成$QwQ$.加一是因为根节点本来不应该减一的因为没有父亲节点,所以就加回来$QwQ$.

然后看第二问.

首先显然先二分出一个长度.然后$check$就$dfs$,对每个点记录一个$dis_i$表示从这个点传来的链的长度.然后每$dfs$到一个点,先把它的子树处理完,将所有传上来的链按长度排序.

然后考虑分类讨论,对于有奇数个儿子的节点,就二分传上去的链的长度最小值是多少

然后对于有偶数个儿子的节点,如果可以一一匹配就直接一一匹配掉.否则考虑可以将最大值单独覆盖后当作奇数个儿子的节点做.昂因为这里我还理解了下才$get$的所以大概港下$QwQ$.

考虑每个点是有个向上传一条链的权限的,所以当有偶数个儿子节点时,就有一个让一条链落单匹配的权限,所以就可以把最长的那条链单独处理之后当作奇数儿子节点的做$QwQ$

$over$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define t(i) edge[i].to
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=10000+10,inf=1e9+10;
int n,head[N],in[N],ed_cnt,as=1,mid,dis[N],stck[N],top;
bool flg,gdgs=1;
struct ed{int to,nxt;}edge[N<<1];

il int read()
{
    rc ch=gc;ri x=0;rb y=1;
    while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
    if(ch=='-')ch=gc,y=0;
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
    return y?x:-x;
}
il void ad(ri x,ri y){edge[++ed_cnt]=(ed){x,head[y]};head[y]=ed_cnt;++in[x];}
il bool jud(ri dat)
{ri l=1,r=top;while(gdgs){if(l==dat)++l;if(r==dat)--r;if(l>=r)return 1;if(stck[l]+stck[r]>mid)return 0;++l,--r;}}
void dfs(ri nw,ri fa)
{
    if(!flg)return;
    e(i,nw)if(t(i)^fa)dfs(t(i),nw);
    top=0;e(i,nw)if(t(i)^fa)stck[++top]=dis[t(i)]+1;
    sort(stck+1,stck+1+top);if(stck[top]>mid){flg=0;return;}
    if(!(top&1)){rp(i,1,top/2)if(stck[i]+stck[top-i+1]>mid){if(nw==1){flg=0;return;}--top;break;}}
    if(top&1)
    {
        ri l=1,r=top;if(!jud(top)){flg=0;return;}
        while(l<r){ri md=(l+r)>>1;if(jud(md))r=md;else l=md+1;}
        dis[nw]=stck[l];
    }
}
il bool check(){memset(dis,0,sizeof(dis));flg=1;dfs(1,1);return flg;}

int main()
{
    freopen("2067.in","r",stdin);freopen("2067.out","w",stdout);
    n=read();rp(i,1,n-1){ri x=read(),y=read();ad(x,y);ad(y,x);}rp(i,1,n)as+=(in[i]-1)/2;
    ri l=1,r=n;while(l<r){mid=(l+r)>>1;if(check())r=mid;else l=mid+1;}printf("%d %d
",as,l);
    return 0;
}

View Code