题解 | #偶数路径2.0#

题目链接

偶数路径2.0

题目描述

给定一棵 $n$ 个节点的树，每个节点有一个权值 $a_i$ 。一条简单路径的权值定义为路径上所有节点权值的最大公约数 (GCD)。你需要统计权值为偶数的简单路径有多少条。

注意：

路径 u -> v 和 v -> u 视为同一条。
单个节点自身也算作一条路径。

解题思路

1. 核心性质：GCD 与偶数

首先，我们需要理解最大公约数 (GCD) 的一个关键性质：

一组整数的 GCD 是偶数，当且仅当这组整数中的每一个数都是偶数。

只要这组数中存在任何一个奇数，它们的 GCD 就必定是奇数。

2. 问题转化

根据上述性质，原问题 “统计路径权值 (GCD) 为偶数的简单路径数量” 就等价于一个更简单的问题：“统计路径上所有节点权值均为偶数的简单路径数量”。

3. 算法设计：连通块计数

一条路径上的所有节点权值都是偶数，意味着这条路径完全由权值为偶数的节点以及连接它们的边构成。

这启发我们，可以把原图中的所有奇数权值节点以及与它们相连的边全部“删除”，只考虑由偶数权值节点组成的子图。这个子图可能不是连通的，它可能由一个或多个连通块组成（形成一个森林）。

任何一条满足条件的路径，都必须完整地处于某一个连通块内部。因此，我们只需要：

找出所有由偶数节点构成的连通块。
对每个连通块，计算其内部包含多少条简单路径。
将所有连通块的结果相加，即为最终答案。

具体步骤:

筛选节点：遍历所有节点，标记出哪些节点的权值是偶数。
遍历与计数：
- 初始化一个 visited 数组，防止重复访问。
- 遍历从 $1$ 到 $n$ 的所有节点。
- 如果当前节点 $i$ 的权值是偶数，并且它还没有被访问过 (!visited[i])，说明我们发现了一个新的、由偶数节点构成的连通块。
- 从节点 $i$ 开始，进行一次深度优先搜索 (DFS) 或广度优先搜索 (BFS)。在搜索过程中，只访问相邻的、同样是偶数权值的、且未被访问过的节点。
- 通过这次遍历，我们可以统计出当前这个连通块的大小，记为 $k$ 。
计算路径数：
- 一个大小为 $k$ 的连通图（在树的子图中，它本身也是一棵树），其内部的简单路径数量为 $\frac{k \cdot (k+1)}{2}$ 。
- 将这个数量累加到全局答案 ans 中。
循环：继续遍历节点，直到所有偶数节点都被访问过。

最终得到的 ans 就是题目的解。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

vector<vector<int>> adj;
vector<bool> is_even;
vector<bool> visited;
long long current_component_size;

void dfs(int u) {
    visited[u] = true;
    current_component_size++;
    for (int v : adj[u]) {
        if (is_even[v] && !visited[v]) {
            dfs(v);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    adj.resize(n + 1);
    is_even.resize(n + 1, false);
    visited.resize(n + 1, false);
    vector<int> a(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] % 2 == 0) {
            is_even[i] = true;
        }
    }

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    long long total_paths = 0;
    for (int i = 1; i <= n; i++) {
        if (is_even[i] && !visited[i]) {
            current_component_size = 0;
            dfs(i);
            total_paths += current_component_size * (current_component_size + 1) / 2;
        }
    }

    cout << total_paths << endl;

    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static List<List<Integer>> adj;
    static boolean[] isEven;
    static boolean[] visited;
    static long currentComponentSize;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        
        isEven = new boolean[n + 1];
        visited = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            int val = sc.nextInt();
            if (val % 2 == 0) {
                isEven[i] = true;
            }
        }

        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        long totalPaths = 0;
        for (int i = 1; i <= n; i++) {
            if (isEven[i] && !visited[i]) {
                currentComponentSize = 0;
                dfs(i);
                totalPaths += currentComponentSize * (currentComponentSize + 1) / 2;
            }
        }
        
        System.out.println(totalPaths);
    }

    private static void dfs(int u) {
        visited[u] = true;
        currentComponentSize++;
        for (int v : adj.get(u)) {
            if (isEven[v] && !visited[v]) {
                dfs(v);
            }
        }
    }
}

import sys

# Increase recursion limit for deep trees
sys.setrecursionlimit(200005)

adj = []
is_even = []
visited = []
current_component_size = 0

def dfs(u):
    global current_component_size
    visited[u] = True
    current_component_size += 1
    for v in adj[u]:
        if is_even[v] and not visited[v]:
            dfs(v)

def solve():
    global adj, is_even, visited, current_component_size
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
        
        a = [0] + list(map(int, sys.stdin.readline().split()))
        is_even = [False] * (n + 1)
        for i in range(1, n + 1):
            if a[i] % 2 == 0:
                is_even[i] = True
        
        adj = [[] for _ in range(n + 1)]
        for _ in range(n - 1):
            u, v = map(int, sys.stdin.readline().split())
            adj[u].append(v)
            adj[v].append(u)
            
        visited = [False] * (n + 1)
        total_paths = 0
        
        for i in range(1, n + 1):
            if is_even[i] and not visited[i]:
                current_component_size = 0
                dfs(i)
                total_paths += current_component_size * (current_component_size + 1) // 2
                
        print(total_paths)

    except (IOError, ValueError):
        return

solve()

算法及复杂度

算法: 图的遍历 (DFS/BFS) + 连通块思想
时间复杂度: 算法的核心是对图进行一次完整的遍历。每个节点和每条边最多被访问一次。因此，总时间复杂度为 $\mathcal{O}(N+M)$ ，在树中 $M=N-1$ ，所以是 $\mathcal{O}(N)$ 。
空间复杂度: 需要使用邻接表来存储树的结构，大小为 $\mathcal{O}(N)$ 。还需要 is_even 和 visited 数组，大小也为 $\mathcal{O}(N)$ 。DFS 的递归调用栈深度在最坏情况下（链状树）也可能是 $\mathcal{O}(N)$ 。因此，总的空间复杂度为 $\mathcal{O}(N)$ 。