方法思路

1. 这道题目要求计算每个节点i的f[i]，即以i为根的子树中节点编号是i的因子的节点个数
2. 最优解法：使用DFS遍历树，并在遍历过程中计算每个节点的f[i]
3. 优化步骤：
   • 预处理每个节点的子树（建立邻接表）
   • 对于每个节点i，遍历其子树中的所有节点j
   • 判断j是否为i的因子，是则f[i]加1
   • 最终将所有f[i]求和

代码实现

Java

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<Integer>[] graph;
    static int[] subtreeNodes;
    static long result = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int root = Integer.parseInt(st.nextToken());
        
        // 初始化图
        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        // 建立邻接表
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph[u].add(v);
            graph[v].add(u);
        }
        
        // 预处理每个节点的子树
        subtreeNodes = new int[n + 1];
        boolean[] visited = new boolean[n + 1];
        
        // 使用DFS建立树形结构并统计每个节点的子树节点数
        dfs(root, -1);
        
        // 计算最终结果
        System.out.println(result);
    }
    
    // DFS遍历树，计算每个节点的f[i]
    static ArrayList<Integer> dfs(int node, int parent) {
        ArrayList<Integer> nodesList = new ArrayList<>();
        nodesList.add(node); // 添加当前节点
        
        for (int child : graph[node]) {
            if (child != parent) {
                ArrayList<Integer> childNodes = dfs(child, node);
                nodesList.addAll(childNodes);
            }
        }
        
        // 计算f[node]：以node为根的子树中，是node因子的节点个数
        int count = 0;
        for (int num : nodesList) {
            if (node % num == 0) {
                count++;
            }
        }
        
        result += count; // 累加到最终结果
        return nodesList;
    }
}

Python

import sys
sys.setrecursionlimit(10**6)

def main():
    # 快速读入
    n, root = map(int, input().split())
    
    # 初始化图
    graph = [[] for _ in range(n + 1)]
    
    # 建立邻接表
    for _ in range(n - 1):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    
    # 全局结果
    result = [0]
    
    # DFS遍历树，计算每个节点的f[i]
    def dfs(node, parent):
        nodes_list = [node]  # 添加当前节点
        
        for child in graph[node]:
            if child != parent:
                child_nodes = dfs(child, node)
                nodes_list.extend(child_nodes)
        
        # 计算f[node]：以node为根的子树中，是node因子的节点个数
        count = 0
        for num in nodes_list:
            if node % num == 0:
                count += 1
        
        result[0] += count  # 累加到最终结果
        return nodes_list
    
    # 从根节点开始DFS
    dfs(root, -1)
    
    # 输出结果
    print(result[0])

if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> graph;
long long result = 0;

// DFS遍历树，计算每个节点的f[i]
vector<int> dfs(int node, int parent) {
    vector<int> nodesList;
    nodesList.push_back(node); // 添加当前节点
    
    for (int child : graph[node]) {
        if (child != parent) {
            vector<int> childNodes = dfs(child, node);
            nodesList.insert(nodesList.end(), childNodes.begin(), childNodes.end());
        }
    }
    
    // 计算f[node]：以node为根的子树中，是node因子的节点个数
    int count = 0;
    for (int num : nodesList) {
        if (node % num == 0) {
            count++;
        }
    }
    
    result += count; // 累加到最终结果
    return nodesList;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, root;
    cin >> n >> root;
    
    // 初始化图
    graph.resize(n + 1);
    
    // 建立邻接表
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    // 从根节点开始DFS
    dfs(root, -1);
    
    // 输出结果
    cout << result << endl;
    
    return 0;
}