思路:计算贡献法

这个题本质上考的就是大家的计算思维。这个通常在ACM/OI中有考察。而在部分好一点的大学中，会开一门课《具体数学》，在学《求和式》一章时，里面也会有涉及到这种思想。

朴素想法

一个朴素的想法是：对每个节点求$f(i)$ ：对于每个$i$ , 我们统计出$i$的子树集合。接下来枚举每个子孙节点，判断是否$j$是$i$的因子，是的话$f(i)+= 1$

写成数学式是:

其中$[表达式]$是艾弗森符号，即逻辑表达式。命题成立则为1，否则为0

交换贡献/交换求和式

很容易发现以上方法复杂度是$O(n^2)$的。我们考虑交换求和顺序，即考虑每个点$i$作为子孙节点，那么他所有的祖先节点$j$ , 如果满足以上关系即答案加一。

具体来讲，我们在做dfs的过程中，维护一个从根到当前节点的set(祖先节点集合)。对每个节点,我们考虑在set力寻找他的倍数$i,2i,3i,...$ 。

写成数学式就是:

set的查找是$O(1)$的 ， 根据欧拉定理，$\sum_{i}^{}\sum_{j = i,2i,3i,...}^{} = O(nlogn)$

至此，我们使用了简单的交换贡献法(从数学上来说，就是交换求和式(见《具体数学》第二章 和式 2.5 一般性方法))。

python

n , x = map(int, input().split()) # 读入
e = [[] for i in range(n + 1)]
for i in range(n - 1): # 建树
    u , v = map(int, input().split())
    e[u].append(v)
    e[v].append(u)

s = set() # 维护father这个集合
ans = 0
def dfs(u, p): 
    global ans
    s.add(u) # 加入father
    for i in range(u , n + 1 , u): # 枚举i的倍数
        if i in s: # 如果i在father中
            ans += 1
    for v in e[u]: # 遍历u的子节点
        if v != p:
            dfs(v, u)
    s.remove(u)
    return 

dfs(x, 0) # 从x开始dfs
print(ans) #  输出答案

c++

#include<bits/stdc++.h>
using namespace std;
const int N=1E5+10;
vector<int>g[N];
unordered_set<int> s;
long long ans = 0;
void dfs(int u, int p, int n) {
    s.insert(u);
    for (int i = u; i <= n; i += u) {
        if (s.find(i) != s.end()) {
            ans += 1;
        }
    }
    for (int v : g[u]) {
        if (v != p) {
            dfs(v, u, n);
        }
    }
    s.erase(u);
}

int main() {
    int n, x;
    cin >> n >> x;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(x, 0, n);
    cout << ans << endl;
    return 0;
}

java

import java.util.*;

class Main{
    
    static int N = (int)1e5+10;
    static List<Integer>[] g = new ArrayList[N];
    static int[] f = new int[N];
    static boolean[] st = new boolean[N];
    static int n;
    static int ans;
    static Set<Integer> set = new HashSet<>();

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        int x = scan.nextInt();
        Arrays.setAll(g, e->new ArrayList<>());
        for (int i=0; i<n-1; i++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            g[a].add(b);
            g[b].add(a);
        }
        dfs(x);
        System.out.println(ans);
        scan.close();
    }

    public static void dfs(int u){
        st[u]=true;
        set.add(u);
        // for (int i=1; i<=n; i++){
        //     if (st[i] && i%u==0) ans++;
        // }
        // for (int i:set){
        //     if (st[i] && i%u==0) ans++;
        // }
        for (int i=u; i<=n; i+=u){
            if (set.contains(i)) ans++;
        }
        for (int x:g[u]){
            if (!st[x]) dfs(x);
        }
        set.remove(u);
        // st[u] = false;
    }
}

题目描述

仙舟罗浮上有一棵建木，据说服下建木生成的神实就可以得到“无尽形寿“的身体，蜕变为长生种。米小游是短生种，因此她很想找到神实。 建木是一棵有$n$个节点的有根树，节点编号为1~n，根节点为$x$

对于编号为$i$的节点，$f(i)$表示以$i$为根的子树中，节点编号是$i$的因子的节点个数。

建木上神实的总数就是$\sum_{i}^{n}f(i)$，米小游想知道建木上神实的总数是多少。

输入描述

第一行包含两个整数$n,x(1\le x,n\le 10^5)$，表示树的节点个数，根节点编号

接下来$n -1$行，每行两个数$u,v(1 ≤u,v≤ n)$，表示一条$u$到$v$的树边。数据保证一定是一棵树。

输出描述

输出包含一个整数，表示建木上神实的总数。

样例

输入

4 4
1 2
4 3
2 4

输出

7

说明

以节点4为根的子树的节点有[1,2,3,4]，其中[1,2,4]是4的因子，f(4)=3.
以节点2为根的子树的节点有[1,2]，其中[1,2]是2的因子，f(2)= 2。
以节点1为根的子树的节点有[1]，其中|1]是1的因子，f(1)= 1。
以节点3为根的子树的节点有[3]，其中[3]是3的因子，f(3)= 1。
总和为1+2+1+3=7