题解：B4339 [中山市赛 2023] 树的改造

· · 题解

Problem

给出两个含 n 个点的树。每次可以选择第一个树的一个结点将与它相连的所有点打上标记，并将连在该点的边全部断开，再添加若干条边。问最少进行多少次这样的操作可以使第一个树和第二个树一样。

Solution

因为每次操作可以可以将一个点的子节点接到它的父亲上从而缩小两点间 1 的距离。所以当 B 树有一条边 (u,v) 而 A 树没有（下文称缺失边）时，要使它们之间有边，最少的修改次数是 u 和 v 之间点的数量。

于是我们枚举找出缺失边 (u,v)。对于 u 到 v 的路径上所有点做一个标记。

对该路径的寻找只需要找到两点的最近公共祖先，再一步一步往上跳并标记直到相遇即可（由于此题时限较长，所以使用较为朴素的做法）。

两点最近公共祖先的求解较为基础，此处不再赘述。

因为对一个点的操作可以断开与之相连的所有边并随意重新连边，所以即使一个点被多条路径重复标记，对答案的贡献也还是 1。

这个时候你可能会疑惑：对于 A 树较 B 树多出来的边（下文称多余边）怎么处理呢？

其实多出来的边必然在缺失边两点的路径上，你在处理少的边的时候可以顺便把它们断掉，因此对答案没有影响。

可以反证：为了保持一个树的形态，需要保证边恒为 n-1，所以每断掉一条边就必须加恰好一条边。由于经过操作后不存在缺失边，边数至少为 n-1 条。若存在一条多余边不在任何一条缺失边两端点的路径上，则总边数为 n 与修改过程中边数始终为 n-1 的前提相违背。所以多余边必然在某条缺失边两点的路径上。

Code

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

const int N=1e6+100;

int n;

vector<int>tr[N];
int f[N][25],dep[N];
int d[N];

void ff(int x,int fa)//建树 
{
    dep[x]=dep[fa]+1;
    f[x][0]=fa;
    for(int y:tr[x])
    {
        if(y==fa) continue;
        ff(y,x);
    }
}

int lca(int x,int y)//求最近公共祖先 
{
    if(dep[y]>dep[x]) swap(x,y);
    for(int i=24;i>=0;i--)
    {
        if(dep[ f[x][i] ]>=dep[y])
            x=f[x][i];
    }
    if(x==y) return x;
    for(int i=24;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        tr[u].push_back(v);
        tr[v].push_back(u);
    }

    ff(1,0);

    for(int k=1;k<=24;k++)
    {
        for(int i=1;i<=n;i++)
            f[i][k]=f[f[i][k-1]][k-1];
    }

    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        int ff=lca(u,v);

        if((ff==u and f[v][0]==ff) or (ff==v and f[u][0]==ff)) continue;

        if(u!=ff and v!=ff) d[ff]++;

        //朴素的往上跳，标记路过的边 
        while(u!=ff and f[u][0]!=ff)
        {
            u=f[u][0];
            d[u]++;
        } 
        while(v!=ff and f[v][0]!=ff)
        {
            v=f[v][0];
            d[v]++;
        } 
    }

    int ans=0;
    for(int i=1;i<=n;i++)
        if(d[i]>0)//对于多次经过的点也只算 1 的贡献
            ans++;
    cout<<ans;
}

感谢 @ 取名真难！提供部分思路。