HDU_2376

? ? 對于任意一棵子樹來講，以根節(jié)點為深度最淺的點的路徑一共有兩類，一類是以根節(jié)點為端點的路徑，另一類是過根節(jié)點但端點分別在兩棵子樹中的路徑。然后將無根樹轉(zhuǎn)化為有根樹后dfs時計算出上面兩類路徑的長度即可。

#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #define MAXD 10010 #define MAXM 20010 typedef long long LL; LL f[MAXD], ANS; int N, first[MAXD], size[MAXD], e, next[MAXM], v[MAXM], w[MAXM]; void add(int x, int y, int z) {v[e] = y, w[e] = z;next[e] = first[x], first[x] = e ++; } void init() {int i, x, y, z;scanf("%d", &N);memset(first, -1, sizeof(first[0]) * N), e = 0;for(i = 1; i < N; i ++){scanf("%d%d%d", &x, &y, &z);add(x, y, z), add(y, x, z);} } struct St {LL f;int size;St(){}St(LL _f, int _size) : f(_f), size(_size){} }; void dfs(int cur, int fa) {int i, s = 0;LL A = 0;size[cur] = 1, f[cur] = 0;std::queue <St> q;for(i = first[cur]; i != -1; i = next[i])if(v[i] != fa){dfs(v[i], cur);size[cur] += size[v[i]], f[cur] += f[v[i]] + w[i] * size[v[i]];q.push(St(f[v[i]] + size[v[i]] * w[i], size[v[i]]));}ANS += f[cur];while(!q.empty()){St st = q.front();q.pop();ANS += st.size * A + s * st.f;s += st.size, A += st.f;} } void solve() {ANS = 0;dfs(0, -1);printf("%.7f\n", (double)ANS * 2 / (N * (N - 1))); } int main() {int t;scanf("%d", &t);while(t --){init();solve();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的HDU 2376 Average distance的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。