递归&&保存路径（回溯）、树的直径

今天莫名其妙负能量爆发惹，还好还有两天就去听GIN🎸的live了……日推的歌还一首比一首远离人世……………没办法集中精神的丧啊…………莫非脑缺氧……刚买的运动耳机，晚上跑步好了 = =

我活了，跟女🦢对骂有奇效嗷，我很满意

分析两道值得仔细磨一磨的题吧 = =

• 求🌲的直径（树上的最长链）
• 树的遍历➕回溯（保存路径），并对路径排序。

1053 Path of Equal Weight (30 分)

• ⚠️对等权重路径的排序：不必，在建树时，排序，可以保证先遍历到符合题意的较大
• ⚠️剪枝：如果当前路径上点权之和已经大于total，直接返回

• ⚠️path的维护：两种方式。

  1. 使用vector，及时push_back，pop_back
  2. 使用数组记录，要在DFS中添加一个参数记录数组中元素个数，以便覆盖、加入新结点。

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
int weight[100] = {0};

vector<int> nodes[100], path;
int nn, mm, total;

bool cmp(const int n1, const int n2) {
    return weight[n1] > weight[n2];
}

void DFS(int root, int temp) {
    if (temp > total) return;
    if (temp == total && nodes[root].empty()) {
        int len = path.size() - 1;
        for (int i = 0; i < len; i++) {
            printf("%d ", weight[path[i]]);
        }
        printf("%d\n", weight[path.back()]);
    }
    for (auto item:nodes[root]) {
        path.emplace_back(item);
        DFS(item, temp + weight[item]);
        path.pop_back();
    }
}

int main() {
    scanf("%d%d%d", &nn, &mm, &total);
    for (int i = 0; i < nn; ++i) {
        scanf("%d", &weight[i]);
    }
    for (int i = 0; i < mm; ++i) {
        int father, cnt, son;
        scanf("%d%d", &father, &cnt);
        for (int j = 0; j < cnt; ++j) {
            scanf("%d", &son);
            nodes[father].emplace_back(son);
        }
        sort(nodes[father].begin(), nodes[father].end(), cmp);
    }
    path.emplace_back(0);
    DFS(0, weight[0]);
    return 0;
}

1021 Deepest Root (25 分)

若图连通、且恰有N — 1 条边，则能确定是一棵树。
（以下找 root 的策略来自「算法笔记」，证明十分精彩！！！这里没有放上来）
下面的任务就是选择合适的根结点，使得树的高度最大。具体做法为：

• 先任意选择一个结点，从该结点开始遍历整棵树，获取能达到的最深的顶点（记为结点集合 A）；
• 然后从集合 A 中任意个结点出发遍历整棵树，获取能达到的最深的顶点（记为结点集合 B）。这样集合 A 与集合 B 的并集即为所求的使树高最大的根结点。

实现

• 算法笔记的解法
  并查集求连通分量、若连通分量仅有1个（是🌲），两次DFS求树的直径。
  ⚠️记录前驱防止无向图无限循环出不来。（若孩子为前驱则continue）
• 下面是我的写法，visited数组记录结点是否已经访问过，BFS求连通分量数，若一次BFS就访问了所有结点，则是🌲，再次初始化visited数组，max_level，再一次BFS……；否则，访问全部结点所需BFS次数即连通分量数。
  ⚠️一定要注意visited数组的更新、重置
  ⚠️用迭代器取集合元素：✳️ （*set1.begin()）
  ⚠️合并集合写法：set1.insert(set2.begin(), set2.end());

#include <cstdio>
#include <vector>
#include <set>
#include <queue>

using namespace std;
bool visited[10001] = {false};
int levels[10001] = {0}, max_level = 0;
vector<int> nodes[10001];
set<int> roots;
int nn;

void BFS(int root) {
    queue<int> mq;
    mq.push(root);
    while (!mq.empty()) {
        int curr = mq.front();
        mq.pop();
        visited[curr] = true;
        for (auto item:nodes[curr]) {
            if (visited[item]) continue; // 无环无向图 防止无穷loop
            mq.push(item);
            levels[item] = levels[curr] + 1;
            if (levels[item] > max_level) {
                max_level = levels[item];
                roots.clear();
            }
            roots.insert(item);
        }
    }
}

int main() {
    scanf("%d", &nn);
    if (nn == 1) {
        puts("1");
        return 0;
    }
    for (int i = 1; i < nn; ++i) {
        int father, son;
        scanf("%d%d", &father, &son);
        nodes[father].emplace_back(son); //无向图
        nodes[son].emplace_back(father);
    }
    int cnt_cc = 0;
    levels[1] = 1;
    for (int i = 1; i <= nn; ++i) {
        if (!visited[i]) {
            BFS(i);
            cnt_cc++;
        }
    }
    if (cnt_cc == 1) {
        set<int> res = roots;
        int new_st = *roots.begin();
        roots.clear();
        fill(visited + 1, visited + nn + 1, false);
        BFS(new_st);
        res.insert(roots.begin(), roots.end());
        for (auto item:res) {
            printf("%d\n", item);
        }
    } else printf("Error: %d components\n", cnt_cc);
    return 0;
}