Guest User

Untitled

a guest
Nov 13th, 2016
533
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.69 KB | None | 0 0
  1. /*
  2. Author - Priyanshu Jain
  3. */
  4. //#include <atomic>
  5. #include <cstdio>
  6. #include <cmath>
  7. #include <cstdlib>
  8. #include <iostream>
  9. #include <vector>
  10. #include <string>
  11. #include <map>
  12. #include <algorithm>
  13. #include <cassert>
  14. #include <cstring>
  15. using namespace std;
  16.  
  17. #define pb push_back
  18. #define mp make_pair
  19. #define nline cout<<"\n"
  20. #define fast ios_base::sync_with_stdio(false)cin.tie(0)
  21. #define ain(A, B, C) assert(IN(A, B, C))
  22. #define ull unsigned long long int
  23. #define ll long long int
  24. #define pii pair<int,int>
  25. #define MAXX 100009
  26. #define fr(a,b,i) for(int i=a;i<b;i++)
  27. #define dbg(x) cout<<"Here we are "<<x<<"\n"
  28. vector<pair<int,int> >G[MAXX];
  29. const int N=50010;
  30. const int LGN=22;
  31. #pragma comment(linker, "/STACK:1000000000")
  32. ll parent[LGN][N],depth[MAXX],vis[MAXX],weight[MAXX];
  33.  
  34. int uplift(int u,int k){
  35.     for(int i=0;i<LGN;i++){
  36.         if(k&1)u=parent[i][u];
  37.         k>>=1;
  38.     }
  39.     return u;
  40. }
  41.  
  42. void dfs(int src){
  43.     vis[src]=1;
  44.     for(int i=0;i<G[src].size();i++){
  45.         int v=G[src][i].first;
  46.         int w=G[src][i].second;
  47.         if(vis[v])continue;
  48.         parent[0][v]=src;
  49.         weight[v]=weight[src]+w;
  50.         depth[v]=depth[src]+1;
  51.         dfs(v);
  52.     }
  53. }
  54.  
  55. void init()
  56. {
  57.     dfs(0);
  58.     for(int i=1;i<LGN;i++){
  59.         for(int j=0;j<N;j++){
  60.             if(parent[i-1][j]!=-1){
  61.                 parent[i][j]=parent[i-1][parent[i-1][j]];
  62.             }
  63.         }
  64.     }
  65. }
  66.  
  67. int lca(int u,int v){
  68.     int diff=abs(depth[u]-depth[v]);
  69.     if(depth[u]>depth[v]){
  70.         u=uplift(u,diff);
  71.     }
  72.     else if(depth[v]>depth[u]){
  73.         v=uplift(v,diff);
  74.     }
  75.     if(u==v)return u;
  76.     for(int i=LGN-1;i>=0;i--){
  77.         if(parent[i][u]!=parent[i][v]){
  78.             u=parent[i][u];
  79.             v=parent[i][v];
  80.         }
  81.     }
  82.  
  83.     return parent[0][u];
  84. }
  85.  
  86.  
  87. unsigned int gcd(unsigned int u, unsigned int v)
  88. {
  89.     int shift;
  90.     if (u == 0) return v;
  91.     if (v == 0) return u;
  92.     shift = __builtin_ctz(u | v);
  93.     u >>= __builtin_ctz(u);
  94.     do {
  95.         v >>= __builtin_ctz(v);
  96.         if (u > v) {
  97.             unsigned int t = v;
  98.             v = u;
  99.             u = t;
  100.         }
  101.         v = v - u;
  102.     } while (v != 0);
  103.     return u << shift;
  104. }
  105.  
  106.  
  107. int main()
  108. {
  109. int t;
  110. cin>>t;
  111. while(t--){
  112.   memset(parent,-1,sizeof parent);
  113.     memset(vis,0,sizeof vis);
  114.     memset(weight,0,sizeof weight);
  115.     int n,m;
  116.     cin>>n>>m;
  117.     for(int i=1;i<=n-1;i++){
  118.         int u,v,w;
  119.         cin>>u>>v>>w;
  120.         G[u-1].pb({v-1,w});
  121.         G[v-1].pb({u-1,w});
  122.     }
  123.   init();
  124.   int a[m],sum=0;
  125.   for(int i=0;i<m;i++){
  126.     cin>>a[i];
  127.   }
  128.   for (size_t i = 0; i < m; i++) {
  129.     for (size_t j = i+1; j < m; j++) {
  130.       int lc=lca(a[i]-1,a[j]-1);
  131.       ll ans=weight[a[i]-1]+weight[a[j]-1]-2*weight[lc];
  132.       sum+=ans;
  133.     }
  134.   }
  135.   int num,den;
  136.   int div = gcd(sum*2,m*m);
  137.   num = sum*2/div;
  138.   den = m*m/div;
  139.   cout<<num<<" "<<den<<endl;
  140. }
  141.     return 0;
  142. }
Add Comment
Please, Sign In to add comment