AHOI2022 回忆 - 自下向上之一

· · 题解

credit https://www.cnblogs.com/chenxiaoran666/p/Luogu8341.html

因为树上贪心一定要从下往上，考虑从下往上贪心。每个点只保留深度最浅的以其为下端点的限制。

称 路径 为直上直下的路径；称两条路径 匹配 为它们能连接起来成为一条路径。

首先，找出所有子树内没有限制下端点，自身又是限制下端点的点，容易证明：一定存在一种最优方案，所有路径的端点都属于这些点。

我们的目标是尽量少开始路径，尽量多匹配路径。

考虑在 x 子树内有哪些路径：

  1. 尚未达到自己目标深度的路径。
  2. 已经达到目标深度，可以匹配的路径。
  3. 已经与匹配的有上有下的路径。

1 类路径只需要特殊处理目标深度最小的这一条，这一条可以用来满足 x 到 1 这条链上其它的限制；其它 1 类路径在达到目标深度后会自动变成 2 类路径，可以在深度上打标记实现。

2,3 类路径可以互相转化（可以把 3 拆成两个 2）。合并两个子树 p,q 时，贪心匹配它们内部的路径。假设 p,q 分别 2 类路径数为 x,y，3 类路径数为 a,b。

发现肯定是用 x,y 小的那一边去匹配大的那一边（因为把内部 3 类路径拆开拿来匹配并不会增加答案）。不妨假设 x<y。

合并完子树后，处理 x 自己开始的贡献。

如果 x 子树内还有 1 类路径没有完结，根据上面的说法，它就是拿来处理这里新加这条这样的路径的。故直接把这条路径拉长。

否则，我们不得不新开一条路径来满足 x 本身的要求。我们可以直接拿出一条 2 类路径，或拆掉一条 3 类路径。如果 2,3 类路径都没有就不得不新开一条路径。（注意！“新开路径”并没有显示在算法中体现，因为我们是在它完成自己任务之后才把它作为可以匹配的路径加进来的，这也是贪心算法的前提。所以，现在这里新开路径不需要做其它操作；反而是拉长一条原本有的路径需要把当前贡献减一。）

整个做法时间复杂度 O(n+m)。

以下瞎扯一下正确性。这个算法自己有一些非常让人信服的点。

  1. 注意到每个限制我们尽量在深的地方拿出来配，越深配在之后能做的事情越多。
  2. 算法的部分内部都显然正确。
  3. 整个过程完全从下往上，符合“树上一定要从下往上而非从上往下”的教训（应该叫 经验）。
int n,m,a[200005],b[200005],d[200005],mn[200005],tag[200005],to[200005];
//a:已经匹配 b:尚未匹配 
vector<int> g[200005];
void dfs1(int x,int fa){
    d[x]=d[fa]+1;
    for(int y:g[x]){
        if(y==fa)continue;
        dfs1(y,x);
    }
}
void dfs2(int x,int fa){
    for(int y:g[x]){
        if(y==fa)continue;
        dfs2(y,x),b[y]+=tag[d[x]],tag[d[x]]=0;
        //y子树内延伸上来的，打在y上
        if(mn[y]==d[x])b[y]++,mn[y]=0;
        if(mn[x]&&mn[y]){
            if(mn[x]<mn[y])tag[mn[y]]++;
            else tag[mn[x]]++,mn[x]=mn[y];
        }
        else mn[x]|=mn[y];
        if(b[x]<b[y])swap(b[x],b[y]),swap(a[x],a[y]);
        if(b[y]+2*a[y]>=b[x]){
            int w=b[x]+b[y]+2*a[y];
            a[x]+=(w>>1),b[x]=(w&1);
        }
        else b[x]-=b[y]+2*a[y],a[x]+=b[y]+2*a[y];
    }
    if(to[x]){
        if(!mn[x]){
            mn[x]=to[x];
            if(b[x])b[x]--;
            else if(a[x])a[x]--,b[x]++;
        }
        else mn[x]=min(mn[x],to[x]);
    }
}
void Solve(){
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),g[x].push_back(y),g[y].push_back(x);
    dfs1(1,0);
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        if(!to[y]||to[y]>d[x])to[y]=d[x];
    }
    dfs2(1,0);
    cout<<a[1]+b[1]<<'\n';
    for(int i=1;i<=n;i++)mn[i]=tag[i]=to[i]=a[i]=b[i]=0,g[i].clear();
}