题解 | 偶数路径2.0

分析

1.gcd：

1. gcd 表示‌最大公约数(Greatest Common Divisor)；
2. 均为偶数：如果一组数据的最大公约数为偶数，由于偶数都能被2整除，所以这组数据的都能被2整除，即都是偶数；
3. 均是偶数：如果一组数据都是偶数，那么这组数据都能被2整除，即存在公因子2，所以他们的最大公约数也一定是2乘以其他整数的结果，即他们的最大公约数能被2整除，即是最大公约数是偶数；
4. 由以上得出结论：一组数据的最大公约数为偶数的充要条件是这组数据都是偶数；因此在该题中，只需要算这个树中所有的偶数子树中的所有偶数不重复双向路径即可。

2.树的结构：

1. 由于题目中明确定义了是树，也就说不存在环型结构， 树有n个节点，就有n-1个边，该题中涉及了奇数偶数的问题还拆分了子树；
2. 由于树中任意两点间有且仅有一条通路，所以有多少条偶数简单路径就转化为了偶数子树有多少个点对；
3. 有多少个点对只需要知道该子树中有多少个点n，那么点对就有 n * (n - 1) / 2 对，即n中取2个的组合公式，再加上n个节点和自己一对，即加上n，则最终公式为有 n * (n + 1) / 2 对，最后累加这些偶数子树即可。

3.计算的简化：

1. 程序无需对其他任何情况有适用性，只需要解出该题的结果即可；
2. 不需要实际的验证有多少个路径，比如实际运行获取所有路径，再去对这些路径做判断，这样做在该题中不但没有意义，还会增加运行时间，导致虽然程序完全没问题但是却无法在指定时间内通过复杂的测试；
3. 这道题只能也只需要求出每个独立树中的点的个数就行，后面的就是单纯的基于知识的快捷求解，也就是不运行但知道的知识点直接输出结果，算是一种“取巧”。

4.运行思路：

1. 输入点值存储，计算点奇偶性存储（本题可不存点值，只算奇偶性）；
2. 输入单独路径后转为每个点对应对应其他所有点的连接关系的映射，这是进行后续遍历的必要条件；
3. 最后是存储访问过的点（在题中有两个功能，1是防止单次遍历时重复往回遍历，因为是双向的，2是防止全点遍历时取之前已经用过的点）；
4. 上述的数据在该题中可直接用原有的值作为下标，用数组对应，从1开始即可；
5. 运算时就是遍历每个节点，在是偶数且没访问过的情况下，执行DFS或者BFS算法遍历得到每个偶数子树的节点数，再用公式累加计算结果即可，这里需要注意遍历执行后访问状态是不回溯的，因为执行过遍历的点则完成了所有计算需要排除在外。

代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;

void dfs(unordered_map<int, unordered_set<int>>& graph,
         vector<bool>& isEven,
         vector<bool>& visited,
         int u,
         int& count) {
    count++;
    visited[u] = true;
    for (int v : graph[u]) {
        if (isEven[v] && !visited[v]) {
            dfs(graph, isEven, visited, v, count);
        }
    }
}

void bfs(unordered_map<int, unordered_set<int>>& graph,
         vector<bool>& isEven,
         vector<bool>& visited,
         int u,
         int& count) {
    queue<int> q;
    q.push(u);
    visited[u] = true;
    while (!q.empty()) {
        u = q.front();
        q.pop();
        count++;
        for (int v : graph[u]) {
            if (isEven[v] && !visited[v]) {
                q.push(v);
                visited[v] = true;
            }
        }
    }
}

int main() {
    int n;
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i < n + 1; i++) {
        cin >> a[i];
    }

    unordered_map<int, unordered_set<int>> graph;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].insert(v);
        graph[v].insert(u);
    }

    vector<bool> isEven(n + 1, false);
    for (int i = 1; i < n + 1; i++) {
        if (a[i] % 2 == 0) {
            isEven[i] = true;
        }
    }

    vector<bool> visited(n + 1, false);

    int result = 0;
    for (int i = 1; i < n + 1; i++) {
        if (isEven[i] && !visited[i]) {
            int count = 0;
            dfs(graph, isEven, visited, i, count);
            // bfs(graph, isEven, visited, i, count); //BFS和DFS任意选择即可
            result += count * (count + 1) / 2;
        }
    }

    cout << result << endl;
}