fork download 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. const int N = 3e5 + 7;
  6. const int LIM = 1000000;
  7. vector<pair<int,int>> g[N];
  8. int n, ans = 0, cntAns = 0;
  9. int siz[N], valid[N], dept[N];
  10. int f[LIM + 5];
  11. vector<int> vec[N];
  12.  
  13. static long long num[LIM + 5], sum[LIM + 5];
  14. static bool used[LIM + 5];
  15. vector<int> usedList;
  16.  
  17. void Count(int u, int p){
  18.     siz[u] = 1;
  19.     for (auto [v,w] : g[u]) if (v != p && !valid[v]){
  20.         Count(v,u); siz[u] += siz[v];
  21.     }
  22. }
  23.  
  24. int Centroid(int u, int p, int half){
  25.     for (auto [v,w] : g[u]) if (v != p && !valid[v] && siz[v] >= half)
  26.         return Centroid(v,u,half);
  27.     return u;
  28. }
  29.  
  30. inline void addNum(int mul, long long d = 0){
  31.     if (!used[mul]) {
  32.         used[mul] = 1;
  33.         usedList.push_back(mul);
  34.     }
  35.     num[mul]++;
  36.     sum[mul] += d;
  37. }
  38.  
  39. void cal(int u, int p, int id){
  40.     if (id == 1){
  41.         int k = vec[u].size();
  42.         for (int mask = 0; mask < (1<<k); ++mask){
  43.             int mul = 1;
  44.             for (int i=0;i<k;i++) if(mask&(1<<i)) mul *= vec[u][i];
  45.             addNum(mul, dept[u]);
  46.         }
  47.     } else {
  48.         int k = vec[u].size();
  49.         for (int mask = 0; mask < (1<<k); ++mask){
  50.             int mul = 1;
  51.             for (int i=0;i<k;i++) if(mask&(1<<i)) mul *= vec[u][i];
  52.             int sign = (__builtin_popcount(mask) % 2 ? -1 : 1);
  53.             ans += sign * (dept[u]*num[mul] + sum[mul]);
  54.             cntAns += sign * num[mul];
  55.         }
  56.     }
  57.  
  58.     for (auto [v,w] : g[u]) if (v != p && !valid[v]){
  59.         dept[v] = dept[u] + w;
  60.         cal(v,u,id);
  61.     }
  62. }
  63.  
  64. void clearMap(){
  65.     for (int x : usedList){
  66.         num[x] = 0;
  67.         sum[x] = 0;
  68.         used[x] = 0;
  69.     }
  70.     usedList.clear();
  71. }
  72.  
  73. void decomp(int u){
  74.     Count(u,0);
  75.     int c = Centroid(u,0,siz[u]/2);
  76.     valid[c] = 1;
  77.  
  78.     clearMap();
  79.     int k = vec[c].size();
  80.     for (int mask = 0; mask < (1<<k); ++mask){
  81.         int mul = 1;
  82.         for (int i=0;i<k;i++) if(mask&(1<<i)) mul *= vec[c][i];
  83.         addNum(mul);
  84.     }
  85.  
  86.     dept[c] = 0;
  87.     for (auto [v,w] : g[c]) if (!valid[v]){
  88.         dept[v] = w;
  89.         cal(v,c,0);
  90.         cal(v,c,1);
  91.     }
  92.  
  93.     for (auto [v,w] : g[c]) if (!valid[v]) decomp(v);
  94. }
  95.  
  96. int32_t main(){
  97.     ios::sync_with_stdio(0);
  98.     cin.tie(0);
  99.  
  100.     cin >> n;
  101.     for (int i=2;i<=n;i++){
  102.         int u,v,w; cin >> u >> v >> w;
  103.         g[u].push_back({v,w});
  104.         g[v].push_back({u,w});
  105.     }
  106.  
  107.     for (int i=2;i<=LIM;i++) f[i]=i;
  108.     for (int i=2;i*i<=LIM;i++) if(f[i]==i)
  109.         for (int j=i*i;j<=LIM;j+=i) if(f[j]==j) f[j]=i;
  110.  
  111.     for (int i=1;i<=n;i++){
  112.         int num=i;
  113.         while(num>1){
  114.             int p=f[num];
  115.             vec[i].push_back(p);
  116.             while(num%p==0) num/=p;
  117.         }
  118.     }
  119.  
  120.     decomp(1);
  121.  
  122.     cout << fixed << setprecision(6);
  123.     cout << (long double)ans / cntAns << '\n';
  124. }
Success #stdin #stdout 0.02s 33148KB
comments (?)
stdin 
Standard input is empty
stdout 
-nan
https://ideone.com/5uePN8
language:
C++14 (gcc 8.3)
created:
12 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!