2020暑期D2-C 思路+证明

2020暑期D2-C 思路+证明
主为自用，欢迎指正。

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

前置知识：
树中链的覆盖，节点A到节点B的经过尽可能少的点的路径（最短路径），亦可以理解成一种遍历经过的路径，经过的点和边都是覆盖。
dfs序，树在dfs遍历时，树的节点出入栈时的序列。

题意：
一颗具有n个节点的树，问是否存在尽可能少的链覆盖所有的节点。

思路：
设s为叶结点数，则连最少存在s/2条，向下取整，可以简单理解链的端点取相邻的节点，路径将最短，即容易出现无法经过祖父节点的情况。结论一，链经过的节点应该尽可能多。
故端点的选择间距尽可能大，容易想到二分叶子节点，将叶子节点分为左右两部分，左边第一个节点与右边第一个节点成链。结论二，链的端点为间隔mid的叶子节点，则可经过尽可能多的节点。（mid=s/2）
若叶子节点s为偶数，则恰好二分，若为奇数，则剩余叶子节点(mid+mid+1)可随意找一个节点成链，推荐根节点（根节点为理论上最难经过的点）。结论三，叶子节点数若为奇数，则让剩余叶子节点与根节点成链。
由于题意需要输出成链的端点，故可以用dfs序找到叶子节点的位置。叶子节点在dfs序中是相邻的数。

代码步骤：

AC代码：

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

int n;
vector <int> g[200005], leap;

void dfs(int pos, int fa) {
    if(g[pos].size() == 1) {leap.push_back(pos); return;}
    for(int i = 0;i < g[pos].size(); i++) {
        if(g[pos][i] == fa) continue;
        dfs(g[pos][i], pos);
    }
}

int main() {
    scanf("%d", &n);
    int u, v, head = 0;
    for(int i = 1;i < n; i++) {
        scanf("%d %d", &u, &v);
        if(!head) head = u;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for(int i = 1;i <= n; i++) {
        if(g[i].size() > 1) {head = i; break;}
    }

    dfs(head, -1);
    int mid = ((int)leap.size()+1)/2;
    printf("%d\n", mid);

    for(int i = 0;i < mid; i++) {
        if(i+mid >= (int)leap.size()) printf("%d %d\n", leap[i], leap[mid]);
        else printf("%d %d\n", leap[i], leap[i+mid]);
    }
}

简单图证：

注：