fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MX = 1e5;
  5. vector<int> primes((MX + 2) / 2, 1);  
  6.  
  7.  
  8. void sieve() {
  9.     primes[0] = 0;  
  10.     for (int i = 3; i * i <= MX; i += 2) {
  11.         if (primes[i >> 1]) {
  12.             for (int j = i * i; j <= MX; j += i) {
  13.                 primes[j >> 1] = 0;
  14.             }
  15.         }
  16.     }
  17. }
  18.  
  19. bool is_prime(int x) {
  20.     if (x == 2) return true;
  21.     if (x % 2 == 0 || x < 2) return false;
  22.     return primes[x >> 1];
  23. }
  24.  
  25. int main() {
  26.     ios::sync_with_stdio(false);
  27.     cin.tie(nullptr);
  28.  
  29.     sieve();  
  30.  
  31.     int n;
  32.     cin >> n;
  33.  
  34.     vector<vector<int>> g(n + 1);
  35.     for (int i = 0; i < n - 1; i++) {
  36.         int u, v;
  37.         cin >> u >> v;
  38.         g[u].push_back(v);
  39.         g[v].push_back(u);
  40.     }
  41.  
  42.     vector<int> size(n + 1), nodes;
  43.     function<void(int, int)> dfs = [&](int u, int parent) {
  44.         nodes.push_back(u);
  45.         for (int v : g[u]) {
  46.             if (v != parent && is_prime(v)) {
  47.                 dfs(v, u);
  48.             }
  49.         }
  50.     };
  51.  
  52.     long long ans = 0;
  53.     for (int u = 1; u <= n; u++) {
  54.         if (is_prime(u)) continue;
  55.         int sum = 0;
  56.         for (int v : g[u]) {
  57.             if (!is_prime(v)) continue;
  58.             if (size[v] == 0) {
  59.                 nodes.clear();
  60.                 dfs(v, -1);
  61.                 for (int x : nodes) {
  62.                     size[x] = nodes.size();
  63.                 }
  64.             }
  65.             ans += 1LL * size[v] * sum;
  66.             sum += size[v];
  67.         }
  68.         ans += sum;
  69.     }
  70.  
  71.     cout << ans << "\n";
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
2
1 2
stdout
copy 
1
https://ideone.com/ePFvgE
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!