2020 China Collegiate Programming Contest Qinhuangdao Site K.Kingdom‘s Power树上贪心

Problem Analysis

题目要求求除走遍所有叶子节点的最小步数。首先考虑树上贪心的做法。

• 对于同一根节点而言，我们优先走到达叶节点的最短的链，因为我们期望经过最长链的次数最小，也就是最后走最长链条。所以我们需要对访问顺序进行排序；
• 由于所有链条都是按照上述规则进行排序，因此对于某个点而言，在贪心取路径的过程中，对于到达的 i i i位置，仅会在 i + 1 i+1 i+1次访问时用到。因为后续的操作回溯到的点时距离根节点更近的父亲节点。

我们可以 O ( n ) O(n) O(n)求出树上所有叶子节点最大深度，同时在求深度的过程中，对子树排序。然后再一个DFS，对每个节点求出走到该节点需要的距离，不断更新维护当前点的位置即可。

#include 
using namespace std;

const int N = 1e6 + 10;
int maxdep[N], dep[N], cas = 0;
vector g[N];

#define pb push_back

void dfs1(int now, int ndep){
    maxdep[now] = dep[now] = ndep;
    for(int i = 0; i