CF1900 紫名选手竟在 OI 赛制的 NOI 模拟赛切掉了 CF 3300*？

· · 题解

思路

OI 赛制模拟赛把这个切了，遂写一篇题解“昭告天下”。

这是一个没有特殊定根、没有反悔贪心的做法。

如果一个点的度数是 d，这个点的每两条边都要共用一条路径，那么显然经过这个点的路径条数至少有 \frac{d(d-1)}{2}。

从上往下做显然不可行，考虑从下往上，如果儿子的度数是 x，那么儿子处的路径至少有 x-1 条用了儿子和父亲连接的边，这些路径可以传上去给父亲用，如果父亲的度数是 y，那么父亲要拿这条边和其他边连接共 y-1 条路径，所以这样做可以节省最多 y-1 条边。

如上图，围绕 2 号点应有 3 条路径，围绕 4 号点应有 10 条路径，但是 5\to 4\to 2、6\to4\to2 等围绕 4 的路径是可以和 4\to 2\to 1、4\to 2\to 3 合并的，可以节省两条路径，实际答案为 3+10-2=11。

仅此而已吗？

并非。注意到如果一个儿子给父亲传上来了一条路径，另一个儿子也给父亲传上来了一条路径，那么这两条路径可以在父亲处接在一起，节省了一条路径。

如上图，2,3 号点分别有 6 条路径，各自往其父亲——1 号点处上传了 3 条路径。1 号点原先需要 1 条路径，但消耗了来自 2,3 号点的路径各一条，实际上产生了 -1 条路径（把原先的两条路径拼起来覆盖 1 号点的需求，相当于少了一条）；2,3 号点上传的路径还各自有 2 条，拼凑起来又省了两条。答案为 1+6+6-2-2=9。其中前一个 -2 是两个儿子上传到 1 的共两条边满足了父亲的需求，后一个 -2 是两个儿子剩余上传的四条边相互拼凑所节省的路径。

这里有两点需要注意：

我们先考虑第二类拼凑的情况，发现有的时候并不是所有上传路径都能用来拼凑的。比如说如果上面那个例子中 2 号点有 10^5 个儿子，当它上传 10^5 条路径的时候 3 号点却只上传了 3 条路径，那么只能拼凑出 3 条（暂不考虑第一类对原有需求的拼凑），贡献只有 -3，2 号点剩下的 10^5-3 条路径则毫无用处。我们把上传上去没有办法进行第二类拼凑的这些 10^5-3 条路径称做限制路径，可以拼凑的则成为自由路径。

什么情况下会产生限制路径呢？显然是有一个儿子上传的路径数量超过总上传路径数量的一半的时候，设总上传路径数为 \text{sum}，最多的儿子上传 \text{mx} 条，产生限制路径当且仅当 \text{mx}>\text{sum}-\text{mx}，即其它的子树所有路径拿来和最多的子树拼都拼不完。此时限制路径条数为 \text{mx}-(\text{sum}-\text{mx})，剩下的为自由路径。

接着考虑第一类拼凑，度数为 d 的父亲最多拿走每个儿子的 d-1 条上传路径进行第一类拼凑，显然拿儿子限制路径肯定更好，拿完了再拿自由路径。注意到只要能拿就一定会拿，因为第一类拼凑用一条路径就有 1 的贡献，第二类产生相同贡献需要两倍的路径。

等父亲的需求被填满之后，儿子就可以随便进行第二类的拼凑了...吗？

还没完。我们已经知道第一类的拼凑更优了，那么我们还可以拿走儿子剩下来的更多边，传给父亲的父亲，父亲的父亲的父亲...用来完成第一类。这么说被父亲剩下来的路径也不能直接用来做第二类，还要继续保存着。

似乎感觉很难实现，实际上我们只要从下往上做，记录下层有多少个自由路径和限制路径传上来即可，随后一层一层处理，注意下层的限制路径经过上传之后可能变成自由路径（可以和父亲的父亲的...的父亲的另外一个子树的一条路径合并），递归到根之后再把剩下来的自由路径两两配对即可。正确性显然。

好像很对的样子为什么我考场上会这么忐忑呢时间复杂度 O(\sum n)。具体实现看代码吧。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 600000;
int T,n,u,v;
long long ans;
vector<int>e[N];
pair<ll,ll> sch(int u,int fa){//返回值 first 是 u 子树内的自由路径条数，second 是限制路径条数
    ll rd = 0,mx = 0,sum1 = 0,sum2 = 0,mxf = 0;
    //rd 记录儿子子树被用作满足 u 的需求的路径条数，sum1 记录自由路径条数，sum2 记录限制路径条数
    //mx 记录上传限制路径最多的子树，mxf 记录和 mx 来自同一子树的自由路径数量，mxf 不能和 mx 配对
    ans += 1ll * e[u].size() * (e[u].size() - 1) / 2;//u 的原始需求路径
    for(auto v : e[u]){
        if(v == fa) continue;
        auto [a,b] = sch(v,u);
        if(b < e[u].size()){//限制路径条数不足以满足 u 对 v 度数减一的需求
            if(a + b < e[u].size()) rd += a + b;//限制路径和自由路径加起来都不够，只能全部丢去满足需求了
            else{//限制路径和自由路径加起来足够满足需求，剩余部分的自由路径
                rd += e[u].size() - 1;
                sum1 += a - (e[u].size() - 1 - b);//剩下这么多自由路径
            }
        }
        else{
            sum1 += a,rd += e[u].size() - 1,sum2 += b - (e[u].size() - 1);//自由路径全部剩下，限制路径剩下一部分
            if(b - (e[u].size() - 1) > mx) mx = b - (e[u].size() - 1),mxf = a;//记录限制路径最多的子树
        }
    }
    ans -= rd;//满足需求消耗的路径条数
    sum2 += sum1 - mxf,sum1 = mxf;//把可以配对的自由路径丢到限制路径里，一起尝试与最多的限制路径配对将其转化为自由路径
    if(mx > sum2 - mx) sum1 += 2 * (sum2 - mx),sum2 -= 2 * (sum2 - mx);//还是没有办法全部消灭，只能配出 sum2-mx 对
    else sum1 += sum2,sum2 = 0;//可以全部配对，全部转化为自由路径
    return {sum1,sum2 + e[u].size() - 1};//额外有度数减一条限制路径，来自于 u 的原始需求，别忘了本来就有度数减一条上传路径
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> T;
    while(T --){
        ans = 0;
        cin >> n;
        for(int i = 1;i <= n;i ++) e[i].clear();
        for(int i = 1;i < n;i ++){
            cin >> u >> v;
            e[u].emplace_back(v),e[v].emplace_back(u);
        }
        auto [a,b] = sch(1,0);
        printf("%lld\n",ans - a / 2);//自由路径两两配对
    }
    return 0;
}

招笑赛时代码