Main » 2013 October 4 » [tyvj]扫地杯 道路修建
7:07 AM [tyvj]扫地杯 道路修建 |
| DFS统计 #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<vector> #include<set> #include<map> #include<string> #include<algorithm> #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) #define N 100100 #define pb push_back using namespace std; typedef long long LL; typedef long double LD; vector<int> g[N]; vector<int> w[N]; int n,m;LL tot=0,cnt[N]; LL gcd(LL a,LL b){if (a%b==0) return b;return gcd(b,a%b);} void small(LL&a,LL&b){LL d=gcd(a,b);a/=d;b/=d;} void DFS(int u,int p) { int i;cnt[u]=1; if (g[u].size()==1) {return;} FOR(i,0,g[u].size()-1) { int v=g[u][i]; if (p!=v) { DFS(v,u); tot+=w[u][i]*cnt[v]*(n-cnt[v]); cnt[u]+=cnt[v]; } } } int main() { ios::sync_with_stdio(false); scanf("%d",&n); int i,v1,v2,v3; FOR(i,1,n-1) { scanf("%d%d%d",&v1,&v2,&v3); g[v1].pb(v2);g[v2].pb(v1);w[v1].pb(v3);w[v2].pb(v3); } LL tn=n; tn=tn*(tn-1)/2; DFS(1,-1); small(tot,tn); printf("%lld/%lld",tot,tn); return 0; } |
|
|
| Total comments: 0 | |