SZN 题解

· · 题解

SZN 题解

贪心+二分

题意简述

给定一棵树，要求将树上的边划分成若干不相交的链，求最少链数并要求最长的链尽可能短，输出最少链数和最长链最短值。

思路分析

第一问：求最少链数

从构建链的过程考虑，若子结点处形成若干链，其链会尝试向父结点拓展，称这种拓展为上传。对于一个结点，若我们已经从其子结点上传了若干链，则该结点对这些链有如下可能操作：

  1. 合并两条链，新链不可继续上传
  2. 向其父结点继续上传某条链
  3. 保持，即不上传也不合并

发现操作二可以被视为子结点上传的链与祖先结点下传的链的合并，而操作三一定不会使答案更优。可以贪心。所以在某个结点处，对于其相邻结点（不再考虑父子关系）传来的链会优先合并，之后若剩余一条链无法合并，将其保持。也就是说会有 \lfloor \frac{deg_u}{2} \rfloor 条链参与合并，合并会使答案 -1，初始可视为有 n-1 条链，故第一问答案为

n-1-\sum_{u\in V} {\lfloor \frac{deg_u}{2} \rfloor}

第二问：求最长链最短值

尝试贪心，对于某个结点，由于无法预知祖先节点的成链情况，只能考虑其子结点上传的链，可能操作同上，因为要保证链数最少，所以依然优先合并，之后上传剩余的链。但发现合并情况未知；同时若子结点数为偶数，最后剩余的两条链不一定合并。原因可以从上文出发，即上传是一种与祖先的合并，祖先情况未知时我们并不知道一条链是与其兄弟链合并更优还是与祖先链合并更优，所以直接贪心失败。

反向思考，发现无法直接贪心的原因为不确定链长限制，导致不确定是否可以合并。但在链长度的上限一定，不保证最少链数的情况下则仍可以贪心：先将所有合并后长度未超过限制的链合并，之后根据限制决定上传还是保持。

于是二分答案，二分链长上限 x，将问题转化为判断问题：由于未保证最少链数，需要判断链长上限为 x 时合并后的总链数是否满足最少链数。

做法实现

建图，统计度数，得第一问答案；对第二问，二分链长上限，搜索链数。在搜索中，对子结点上传的链按长度排序，枚举最长链，尝试将当前最长链与合并后长度不大于但最接近二分答案的链合并，若无法找到这另一条链，则只能上传或保持。最终一个结点上传的链长是其未能合并链中最短的，若全部合并，上传值为 0。最终别忘了根节点无法上传链，所有没能合并的链都将保持。

该题解曾经被 hack，原因是之前笔者在做法上尝试使用最长链直接与最短链合并，这显然是不对的，十分小丑，在此谢罪。

Code

#include<bits/stdc++.h>
using namespace std;
int const N=10005;
int n,x,y,num,ans,cnt,dg[N],len[N],head[N];
struct edge {int to,nxt;} e[N<<1];
void addin(int x,int y)
{
    e[++cnt]={y,head[x]},head[x]=cnt,dg[y]++;
    e[++cnt]={x,head[y]},head[y]=cnt,dg[x]++;
}
void dfs(int u,int p,int x)
{
    if(dg[u]==1&&u!=1) return len[u]=0,void();
    multiset<int> tmp; tmp.clear(),len[u]=0;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==p) continue;
        dfs(v,u,x),tmp.insert(len[v]+1);
    }
    while(tmp.size())
    {
        auto lst=tmp.end(); lst--;
        int tmplen=(*lst);
        tmp.erase(lst);
        auto it=tmp.upper_bound(x-tmplen);
        if(it==tmp.begin()) len[u]=tmplen,ans++;
        else it--,tmp.erase(it),ans++;
    }
    if(!len[u]) return;
    len[u]+1<=x?ans--:len[u]=0;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n,num=n-1;
    for(int i=1;i<n;i++) cin>>x>>y,addin(x,y);
    for(int i=1;i<=n;i++) num-=dg[i]/2;
    int l=1,r=n-1,mid;
    while(l<r)
    {
        mid=(l+r)/2,ans=0,dfs(1,0,mid);
        ans+=(len[1]?1:0),ans>num?l=mid+1:r=mid;
    }
    cout<<num<<" "<<l<<endl,exit(0);
}