fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl '\n'
  4. int arr[100005],size[100005];
  5. long long res[100005];
  6. std::vector< vector< pair<int,int> > > v(100005);
  7. void initialize(int n)
  8. {
  9. 	for(int i=1;i<=n;i++)
  10. 	{
  11. 		size[i]=1;
  12. 		arr[i]=i;
  13. 	}
  14. }
  15. int root(int i)
  16. {
  17. 	while( arr[i] != i)
  18. 	{
  19. 		arr[i]=arr[arr[i]];
  20. 		i=arr[i];
  21. 	}
  22. 	return i;
  23. }
  24. bool find(int a,int b)
  25. {
  26. 	if(root(a)==root(b))
  27. 		return true;
  28. 	return false;
  29. }
  30. void weighted_union(int a,int b)
  31. {
  32. 	int ra=root(a);
  33. 	int rb=root(b);
  34. 	if(ra==rb)
  35. 		return;
  36. 	if(size[ra]<size[rb])
  37. 	{
  38. 		arr[ra]=arr[rb];
  39. 		size[rb]+=size[ra];
  40. 		size[ra]=0;
  41. 	}
  42. 	else
  43. 	{
  44. 		arr[rb]=arr[ra];
  45. 		size[ra]+=size[rb];
  46. 		size[rb]=0;
  47. 	}
  48. }
  49. int main()
  50. {
  51.     ios_base::sync_with_stdio(false);
  52.     cin.tie(NULL);
  53.    	int n,q;
  54.     cin>>n>>q;
  55.     for(int i=1;i<n;i++)
  56.     {
  57.       int a,b,c;
  58.       cin>>a>>b>>c;
  59.       int lim=ceil((double)sqrt(c));
  60.       for(int i=1;i<=lim;i++)
  61.       {
  62.         if(c%i ==0)
  63.         {
  64.           if(c/i == i)
  65.           {
  66.             v[i].push_back(make_pair(a,b));
  67.           }
  68.           else
  69.           {
  70.             v[i].push_back(make_pair(a,b));
  71.             v[c/i].push_back(make_pair(a,b));
  72.           }
  73.         }
  74.       }
  75.  
  76.     }
  77.     initialize(n);
  78.     for(int d=1;d<=100000;d++)
  79.     {
  80.       for(int i=0;i<v[d].size();i++)
  81.       {
  82.         weighted_union(v[d][i].first,v[d][i].second);
  83.       }
  84.       unordered_set<int> s;
  85.       for(int i=0;i<v[d].size();i++)
  86.       {
  87.           s.insert(root(v[d][i].first));
  88.           s.insert(root(v[d][i].second));
  89.       }
  90.       long long ans=0;
  91.       for(auto it=s.begin();it != s.end();it++)
  92.       {
  93.         long long co = size[*it];
  94.         ans+= (co*(co-1))/2;
  95.       }
  96.       res[d]=ans;
  97.       for(int i=0;i<v[d].size();i++)
  98.       {
  99.  
  100.         arr[v[d][i].first]=v[d][i].first;
  101.         size[v[d][i].first]=1;
  102.  
  103.         arr[v[d][i].second]=v[d][i].second;
  104.         size[v[d][i].second]=1;  
  105.       }  
  106.     }
  107.     while(q--)
  108.     {
  109.       int d;
  110.       cin>>d;
  111.       cout<<res[d]<<endl;
  112.  
  113.     }
  114.     return 0;
  115. }
  116.  
Runtime error #stdin #stdout 0s 5932KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yFqT8a
language:
C++14 (gcc 8.3)
created:
6 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!