fork download
copy 
  1. #include <bits/stdc++.h>`
  2.  
  3. #define slld(longvalue) scanf("%d", &longvalue)
  4.  
  5. #define ll int
  6. #define ull unsigned long long
  7. #define pll pair < int,int >
  8.  
  9. #define fastio ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0)
  10.  
  11. #define pb(x) push_back(x)
  12.  
  13. #define bug printf("BUG\n")
  14.  
  15. #define mxlld LLONG_MAX
  16. #define mnlld -LLONG_MAX
  17.  
  18. #define mxd 2e8
  19. #define mnd -2e8
  20.  
  21. #define pi 3.14159265359
  22.  
  23. #define mod 1000000009
  24.  
  25.  
  26. using namespace std;
  27.  
  28. bool check(ll n, ll pos)
  29. {
  30.     return n & (1LL << pos);
  31. }
  32.  
  33. ll Set(ll n, ll pos)
  34. {
  35.     return n = n | (1LL << pos);
  36. }
  37.  
  38.  
  39. vector < pll > graph[1000005];
  40. ll dp[1000005];
  41. ll dp2[1000005];
  42. ll subnode[1000005];
  43. ll subnode2[1000005];
  44. ll degree[1000005];
  45.  
  46. const ll maxn = 1000000;
  47. bool vis[maxn+10];
  48.  
  49. void sieve()
  50. {
  51.     vis[0] = 1;
  52.     vis[1] = 1;
  53.  
  54.     for(ll i = 4; i <= maxn; i += 2)
  55.     {
  56.         vis[i] = 1;
  57.     }
  58.  
  59.     for(ll i = 3; i * i <= maxn; i += 2)
  60.     {
  61.         if(vis[i] == 0)
  62.         for(ll j = i * i; j <= maxn; j += i)
  63.         {
  64.             vis[j] = 1;
  65.         }
  66.     }
  67.  
  68. }
  69.  
  70. ll beauty(ll x)
  71. {
  72.     return vis[x] == 0;
  73. }
  74.  
  75. void dfs(ll node, ll par)
  76. {
  77.     dp[node] = 0;
  78.     subnode[node] = 0;
  79.  
  80. //    cout << node << " " << par << endl;
  81.  
  82.     for(auto it:graph[node])
  83.     {
  84.         if(it.first == par) continue;
  85.  
  86.         dfs(it.first,node);
  87.  
  88.         subnode[node] += subnode[it.first];
  89.  
  90.         if(it.second)
  91.         {
  92.             dp[node] += subnode[it.first];
  93.         }
  94.         else
  95.         {
  96.             dp[node] += dp[it.first];
  97.         }
  98.     }
  99.  
  100.     subnode[node] += 1;
  101. }
  102.  
  103. void solve(ll node, ll par, ll conn)
  104. {
  105.     if(par)
  106.     {
  107.         if(conn)
  108.         {
  109.             dp2[node] = subnode2[par];
  110.         }
  111.         else
  112.         {
  113.             dp2[node] = dp2[par];
  114.  
  115.             dp2[node] -= dp[node];
  116.         }
  117.     }
  118.  
  119.     dp2[node] += dp[node];
  120.  
  121.  
  122.     for(auto it:graph[node])
  123.     {
  124.         if(it.first == par) continue;
  125.  
  126.         subnode2[node] = subnode2[par] + subnode[node] - subnode[it.first];
  127.  
  128.         solve(it.first,node,it.second);
  129.     }
  130. }
  131. int main()
  132. {
  133.     ll i, j, k, l, m, n, o, r, q;
  134.     ll testcase;
  135.     ll input, flag, tag, ans;
  136.  
  137. //    freopen("in9.txt", "r", stdin);
  138. //
  139. //    freopen("out09.txt", "w", stdout);
  140.  
  141.     sieve();
  142.  
  143.     slld(n);
  144.     {
  145. //        precal(n);
  146.         assert(2 <= n && n <= 1000000);
  147.  
  148.         for(i = 1; i < n; i++)
  149.         {
  150.             ll u, v, w;
  151.  
  152.             slld(u);
  153.             slld(v);
  154.             slld(w);
  155.  
  156.             assert(1 <= u && u <= n);
  157.             assert(1 <= v && v <= n);
  158.             assert(1 <= w && w <= 1000000);
  159.             assert(u != v);
  160.  
  161.             w = beauty(w);
  162.  
  163.             graph[u].push_back(make_pair(v,w));
  164.             graph[v].push_back(make_pair(u,w));
  165.  
  166.             degree[u]++;
  167.             degree[v]++;
  168.         }
  169.  
  170.         ll root = 0;
  171.  
  172. //        bug;
  173.  
  174.         for(i = 1; i <= n; i++)
  175.         {
  176.             if(degree[i] == 1)
  177.             {
  178.                 root = i;
  179.                 dfs(i,-1);
  180.                 break;
  181.             }
  182.         }
  183.  
  184.         solve(root,0,0);
  185.  
  186.  
  187.         long long anss = 0;
  188.  
  189.         for(i = 1; i <= n; i++)
  190.         {
  191.             anss += ((long long)dp2[i] * (long long)(dp2[i] - 1));
  192.         }
  193.  
  194.  
  195.         printf("%lld\n", anss);
  196.  
  197.     }
  198. }
  199.  
  200.  
  201.  
  202.  
  203.  
Runtime error #stdin #stdout #stderr 0.01s 27788KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:146: int main(): Assertion `2 <= n && n <= 1000000' failed.
https://ideone.com/3mlW6u
language:
C++ (gcc 8.3)
created:
4 years 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!