Untitled

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<int> precompute_factors_count(int N) {
    vector<int> factors_count(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        for (int j = i; j <= N; j += i) {
            factors_count[j]++;
        }
    }
    return factors_count;
}

int dfs(int node, int parent, const unordered_map<int, vector<int>>& tree, 
         const vector<int>& factors_count, vector<int>& beauties) {
    int current_beauty = 0;
    
    for (int neighbor : tree.at(node)) {
        if (neighbor == parent) continue; // Avoid going back to the parent
        int child_beauty = dfs(neighbor, node, tree, factors_count, beauties);
        current_beauty += child_beauty;
    }
    
    // Add the factors of the current node
    if (node != 1) { // Skip for root
        current_beauty += factors_count[node];
    }
    
    beauties[node] = current_beauty;
    return current_beauty;
}

int calculate_sum_of_beauties(int N, const vector<pair<int, int>>& edges) {
    unordered_map<int, vector<int>> tree;

    // Build the tree
    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    // Precompute factor counts
    vector<int> factors_count = precompute_factors_count(N);
    
    // Initialize beauties array
    vector<int> beauties(N + 1, 0);
    
    // Perform DFS from the root (node 1)
    dfs(1, -1, tree, factors_count, beauties);

    // Calculate the total sum of A[u]
    long long total_sum = 0;
    const int MOD = 100003;
    for (int u = 1; u <= N; ++u) {
        if (u != 1) { // Skip root for A[u]
            total_sum += (static_cast<long long>(beauties[u]) * u) % MOD + 1;
            total_sum %= MOD;
        }
    }

    return total_sum;
}

// Example usage
int main() {
    int N = 5; // number of nodes
    vector<pair<int, int>> E = {{1, 2}, {1, 3}, {2, 4}, {2, 5}}; // edges
    cout << calculate_sum_of_beauties(N, E) << endl;
    return 0;
}