题解：CF2131D Arboris Contractio

· · 题解

题意

给定一棵无根树 T，有 n 个节点，现有一种操作：

  1. 选择两个节点 s,t\in T。
  2. 把 s 到 t 的简单路径上的每一个节点，断掉原来位于这条链上的边，直接连到 s 节点上

问最少多少次操作才能让 n-1 个节点全部连到另一个节点上

思路

我们注意到这样一个性质：

对于一个选出的根节点 rt\in T，其叶子节点中深度不为 1（就是不直接连接 rt 的叶子节点）都需要至少一次操作来将其连到 rt 上，同时路径上的其它点也一起连好了。

然而，一次操作只能改变一个叶子节点，因为我们必须设定 s 为 rt，否则只会更劣。

这说明什么？

这说明我们只需要操心叶子节点。

更进一步，操作次数就是需要动的叶子节点个数，也就是不直连 rt 的叶子节点个数。

问题来了，对于每一个 rt，我们去求这个东西，是 O(n^2) 的，怎么办？

正难则反，我们只需要先从任意一点出发，求总叶子节点个数，然后对于每一个 rt，分别更新答案。

设以 rt 为根的操作数为 ans_{rt}，总叶子节点个数为 num，以该节点为根时深度为 1 的叶子节点个数为 d1_{rt}，则有

\forall rt\in T, ans_{rt}=num-d1_{rt}

所以我们只要对每一个节点算出答案，再求 \min 就可以了。

复杂度

时间复杂度

我们考虑预处理出总叶子节点个数，以及每一个节点直连叶子节点个数，这是 O(n) 的。

对于每一个节点，算该节点为根答案所需的两个参数我们已经计算好，就是 O(1) 的。

总共 n 个节点，每个节点 O(1)，合起来就是 O(n)。

空间复杂度

我们的信息都是对于每一个节点存的，有 n 个节点，所以是 O(n)。

实现

通过分开 dfs 来进行预处理和计算每一个节点的答案。

在预处理 dfs 完了之后，需要判一下目前作根的点是否只有一个子节点，如果是，总叶子节点个数要 +1。

注意，特判 n=2 的情况，因为两个点都会被计算进总叶子节点，但是只能减去一个。

另外，减少时间消耗小技巧：在判断是否为叶子节点时，不需要算完有多少子节点，大于某个值直接返回就行了，因为不是叶子，这也确保了这个操作是 O(1) 的。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct edge
{
    int to,nxt;
} e[500010];
int head[500010],cnt,ans,son,sl[500050],num[500010];
inline void add(int u,int v)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int check(int u,int f)
{
    int sum=0;
    for(int i=head[u];i!=0&&sum<=1;i=e[i].nxt)
    {
        int v=e[i].to;
        if(f!=v) sum++;
    }
    return sum;
}
void dfs1(int u,int f)
{
    num[u]=1;
    sl[u]=0;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v!=f)  
        {
            num[u]++;
            if(!check(v,u)) sl[u]++,son++;
            dfs1(v,u);
        }
    }
}
void dfs2(int u,int f)
{
    ans=max(ans,sl[u]);
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v!=f) dfs2(v,u);
    }
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n; 
        cnt=ans=son=0;
        for(int i=0;i<=2*n;i++) head[i]=0,e[i]={0,0},num[i]=0,sl[i]=0; 
        for(int i=1;i<n;i++)
        {
            int u,v;
            cin>>u>>v;
            add(u,v);
            add(v,u);
        }                                   
        if(n==2) {cout<<"0\n";continue;}
        dfs1(1,0);
        if(check(1,0)==1) 
        {
            son++;
            for(int i=head[1];i;i=e[i].nxt) 
            {
                int v=e[i].to;
                if(v!=0) sl[v]++;
            }
        }
        dfs2(1,0);
        cout<<son-ans<<endl;
    }
    return 0;
}

完结撒花！

碎碎念：机房某位大佬看到是树的题就跳了，但是水到我这个蒟蒻都可以过