2020牛客暑期多校训练营（第二场）C. Cover the Tree

发表于 更新于 分类于

链接

https://ac.nowcoder.com/acm/contest/5667/C

题意

在无根树中选择最少的链覆盖所有的边至少一次

思路

选择一个非叶子节点为根，按照 DFS 序记录下所有叶子

记 $l[i]$ 为按 DFS 序排序后排为 $i$ 的叶子节点，$cnt$ 为叶子个数

当 $cnt$ 为偶数，构造的链为 $l[i]\rightarrow l[cnt/2+1],l[i+1]->l[cnt/2+2],…,l[cnt/2]\rightarrow l[cnt]$

设某条边的儿子节点所覆盖的叶子节点的区间为 $[L,R]$

当 $R\le cnt/2$，这条边会被 $l[R]\rightarrow l[R+cnt/2]$ 覆盖

当 $L>cnt/2$，这条边会被 $l[L-cnt/2]\rightarrow l[L]$ 覆盖

否则因为根的度大于 $1$，所以 $L\ne 1$，$R\ne cnt$ 必有一个条件满足，若 $L\ne 1$，这条边会被 $l[1]\rightarrow l[cnt/2+1]$ 覆盖，若 $R\ne cnt$，这条边会被 $l[cnt/2]\rightarrow l[cnt]$ 覆盖

当 $cnt$ 为奇数，则给匹配剩下那个叶子节点随意匹配一个叶子节点即可

如果以一个叶子节点为根，将根加在按 DFS​ 序排序后的叶子节点的数组最后即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,cnt[N],lf[N],tot;
vector<int> G[N];
void dfs(int u,int fa) {
    cnt[u]=0;
    for(auto v:G[u]) {
        if(v==fa) continue;
        dfs(v,u);
        cnt[u]++;
    }
    if(!cnt[u]||u==1&&cnt[u]==1) lf[++tot]=u;
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<n;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v),G[v].push_back(u);
    }
    dfs(1,0);
    printf("%d\n",tot+1>>1);
    for(int i=1;i<=tot/2;i++) printf("%d %d\n",lf[i],lf[tot-i+1]);
    if(tot&1) printf("%d %d\n",lf[tot/2+1],1);
    return 0;
}