0313携程笔试开发方向第四题思路代码

思路：前提条件，两个数如果他们的最大公约数是偶数，则代表这两个数也一定是偶数。因此，只需要找出树上的偶数连通块，对于每个连通块可以任意选择其中的一个或者二个节点组成简单路径。使用并查集完成对连通块的维护。

#include <iostream>
#include <vector>
using namespace std;
vector<int> g;
int find(int x) {
    if (g[x] == x)return x;
    return g[x] = find(g[x]);
}
int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    g.resize(n + 1);
    for (int i = 1; i <= n; i++) g[i] = i;
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        if (arr[x - 1] % 2 == 0 && arr[y - 1] % 2 == 0) {
            int a = find(x);
            int b = find(y);
            if (a != b) g[a] = b;
        }
    }
    int answer = 0;
    vector<int> cnt(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        if(arr[i - 1] % 2 == 0) cnt[find(i)]++;
    }
    for (int i = 1; i <= n; i++) answer += cnt[i] * (cnt[i] - 1) / 2 + cnt[i];
    cout << answer << endl;
    return 0;
}