fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define x first
  3. #define y second
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. const ll mod = 1e9+9;
  8. vector<pair<int ,ll> > adj[50010];
  9. ll fact[50010], inv[50010], weight[50010];
  10. int d[50010], pa[20][50010];
  11.  
  12. ll power(ll b, ll e = mod-2LL) {
  13.     ll c=1;
  14.     while(e) {
  15.         if(e&1LL)   c=(c*b)%mod;
  16.         b=(b*b)%mod;
  17.         e/=2LL;
  18.     }
  19.     return c;
  20. }
  21.  
  22. void pre() {
  23.     int i, j;
  24.     fact[0]=inv[0]=1;
  25.     for(i=1; i<=50001; ++i) {
  26.         fact[i]=(fact[i-1]*1LL*i)%mod;
  27.         inv[i]=power(i);
  28.     }
  29.     return;
  30. }
  31.  
  32. void dfs(int s, int p, int di, ll z) {
  33.     d[s]=di;
  34.     weight[s]=z;
  35.     pa[0][s]=p;
  36.     for(int i=0; i<adj[s].size(); ++i) {
  37.         int v=adj[s][i].x;
  38.         if(v!=p) {
  39.             dfs(v, s, di+1, z+adj[s][i].y);
  40.         }
  41.     }
  42.     return;
  43. }
  44.  
  45. int LCA(int u, int v) {
  46. 	if(d[u] < d[v]) swap(u,v);
  47. 	int diff = d[u] - d[v];
  48. 	for(int i=0; i<20; i++) if( (diff>>i)&1 ) u = pa[i][u];
  49. 	if(u == v) return u;
  50. 	for(int i=20-1; i>=0; i--) if(pa[i][u] != pa[i][v]) {
  51. 		u = pa[i][u];
  52. 		v = pa[i][v];
  53. 	}
  54. 	return pa[0][u];
  55. }
  56.  
  57. int main() {
  58.     /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
  59.     int i, j, n, u, v;
  60.     ll w;
  61.     pre();
  62.     cin>>n;
  63.     for(i=1; i<n; ++i) {
  64.         cin>>u>>v>>w;
  65.         adj[u].push_back({v, w});
  66.         adj[v].push_back({u, w});
  67.     }
  68.     for(i=0; i<20; ++i)
  69.             for(j=1; j<=n; ++j)
  70.                 pa[i][j]=-1;
  71.     dfs(1, 0, 0, 0);
  72.     ll ans=0;
  73.     for(i=1; i<20; ++i)
  74.         for(j=1; j<=n; ++j)
  75.             if(pa[i-1][j]!=-1)
  76.                 pa[i][j]=pa[i-1][pa[i-1][j]];
  77.     for(i=1; i<=n; ++i) {
  78.         for(j=i+1; j<=n; ++j) {
  79.             int zz;
  80.             zz=LCA(i, j);
  81.             int qq=d[i]+d[j]-2*d[zz];
  82.             ll pp=weight[i]+weight[j]-2*weight[zz];
  83.             ll aux=fact[n];
  84.             pp%=mod;
  85.             aux=(aux*inv[qq+1])%mod;
  86.             aux=(aux*2LL*pp)%mod;
  87.             ans=(ans+aux)%mod;
  88.             //cout<<i<<" "<<j<<" "<<qq<<" "<<pp<<" "<<ans<<endl;
  89.         }
  90.     }
  91.     cout<<ans;
  92.     return 0;
  93. }
  94.  
Runtime error #stdin #stdout 0.02s 9336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/l7gPkz
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!