题解 P6142 【[USACO20FEB]Delegation P】

奇米 · 2020-04-18 20:55:19 · 题解

题解 - \mathrm{P6142 \ [USACO20FEB] \ Delegation\ P}

\huge\color{blue}\boxed{\color{Violet}\mathfrak{There\ is \ my \ blog}}

题目意思

• P6142
• 给定一棵含有n个结点的树，把它分成若干条链（边只能选一次，点可以选多次），使得最短的那条链的长度最长是多少。
• n\leq 10^5

\mathrm{Sol}

• 一道STL良（凉）好练习题。
• 我们首先肯定会去二分答案L那个最长链长，关键是如何判定。
• 我们这边利用multiset这个东东来维护，它是什么讷？就是一个容器，然后加入元素会帮你从小到大排序，且允许加入重复的元素，且删增操作是log的。
• 然后我们就有考虑如何去判定：对于一个节点u有若干条从v连过来的边，我们尽量找道两条链l1,l2连接使得l1+l2尽量接近且大于等于L。这个还是简单易懂的。于是我们是两两配对所以u要从儿子节点v连过来并且要有一条边给自己的父亲节点f_u，那么如果从儿子那儿有奇数条边那么就不管了，如果偶数条边，我们强制构造出奇数条边（即加入一条0边）。
• 于是我们O(n\log^2 n)做完了这道题目，似乎还可以双指针优化到O(n\log n)，这儿不多加介绍（因为比较菜。

\mathrm{Code}

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

inline int read()
{
    int sum=0,ff=1; char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') ff=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        sum=sum*10+(ch^48),ch=getchar();
    return sum*ff;
}

const int N=1e5+5;

int n,m,ans,flg,jb,f[N];
vector<int> G[N];

inline void dfs(int u,int fa,int L)
{
    multiset<int> M;//multiset容器
    if(flg) return;
    for ( int i=0;i<G[u].size();i++ )
    {
        int v=G[u][i];
        if(v==fa) continue;
        dfs(v,u,L);
        M.insert(f[v]+1);
    }
    jb=0;
    if((u==1&&M.size()&1)||(u!=1&&!(M.size()&1))) M.insert(0);
    //强制除根节点外的点从儿子连边过来的边数为奇数条
    while(M.size())
    {
        multiset<int>::iterator It=M.begin();//取当前最小边
        int small=*It;
        M.erase(It);
        multiset<int>::iterator Big=M.lower_bound(L-small);
        //二分找到第一条大于等于二分的L的边
        if(u==1) 
        {
            if(Big==M.end())//找不到，走人
            {
                flg=1;
                break;
            }
            M.erase(Big);
        }
        else 
        {
            if(Big==M.end()&&jb)
            {
                flg=1;
                break;
            }
            if(Big==M.end()&&!jb) 
                jb=1,f[u]=small;//找到那一条可以给f[u]造成贡献的边
            if(Big!=M.end()) M.erase(Big);
        }
    }
}

inline bool check(int mid)
{
    flg=0;
    memset(f,0,sizeof f);
    dfs(1,0,mid);
    return (!flg);
}

int main()
{
    n=read();
    for ( int i=1;i<n;i++ )
    {
        int x,y;
        x=read(),y=read();
        G[x].pb(y);
        G[y].pb(x);
    }
    int l=0,r=n;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid)) 
            l=mid+1,ans=mid;
        else r=mid-1;//二分答案
    }
    printf("%d\n",ans);
    return 0;
}