原題地址這個(gè)算法是由本沙茶在現(xiàn)場(chǎng)使用的那個(gè)做法擴(kuò)展得來的……其實(shí)AC不了，后兩個(gè)點(diǎn)會(huì)因?yàn)槌?shù)過大而T掉……但在BZOJ上算總時(shí)間的話能AC……
首先考慮樹的情形。設(shè)F[i]為從點(diǎn)i開始，往子樹i里面走，到達(dá)葉結(jié)點(diǎn)的期望長度，則很容易得到遞推公式：
F[i] = (ΣF[j] + W(i, j)) / K，其中j是i的子結(jié)點(diǎn)，K是i的子結(jié)點(diǎn)個(gè)數(shù)。
至于這個(gè)式子的證明……很容易搞的，就不說了囧。
這樣，可以在O(N)時(shí)間內(nèi)求出以樹根為起點(diǎn)的期望長度。那么，以其它點(diǎn)為起點(diǎn)的期望長度如何得到？
我們定義一種“扭根”操作（類似平衡樹中的旋轉(zhuǎn)），可以把根結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)“扭”到根上，并使根結(jié)點(diǎn)作為它的子結(jié)點(diǎn)（也就是把父子關(guān)系交換一下）。容易發(fā)現(xiàn)，每次“扭根”之后，只有原來的根結(jié)點(diǎn)和現(xiàn)在的根結(jié)點(diǎn)這兩個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)發(fā)生了變化，因此，也只有這兩個(gè)結(jié)點(diǎn)的F值可能發(fā)生變化，只需要重新求一下即可（其實(shí)不用重新求，只需要維護(hù)一個(gè)KS[]值表示某個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)，然后在維護(hù)的時(shí)候加上或減去相應(yīng)項(xiàng)，并維護(hù)KS即可，這樣可以確保每次維護(hù)的時(shí)間復(fù)雜度為O(1)）。注意“扭根”的順序，需要按照DFS序，而且在遍歷完一個(gè)結(jié)點(diǎn)回退的時(shí)候也要順便“扭”回來。這樣，就可以在O(N)的時(shí)間內(nèi)得出以每個(gè)點(diǎn)為起點(diǎn)的期望長度，取它們的平均值即可。
然后考慮有環(huán)的情形，注意到，環(huán)上的結(jié)點(diǎn)數(shù)很少。由于只有一個(gè)環(huán)，所以先化為無向環(huán)套樹形式。
設(shè)A為環(huán)上的一個(gè)結(jié)點(diǎn)。從A開始走，有可能走到它自己的樹里，也有可能沿著環(huán)走到其它樹里，但是，
A在環(huán)上的兩條鄰邊不可能都走到。也就是，可以枚舉是左鄰邊走不到還是右鄰邊走不到，并將這條邊刪除（反正走不到，要了不如不要），這樣就變成了一棵樹，對(duì)這棵樹按照上面的算法求F值，即可求出以A為起點(diǎn)，
某一條鄰邊走不到情況下的期望長度。這里需要特別注意的是，在求F[A]時(shí)，最后除的那個(gè)數(shù)不是K，而是(K+1)，因?yàn)殡m然這條鄰邊刪掉了，但為了防止它走到還是要考慮一下的 。設(shè)F1[A]為A的左鄰邊走不到時(shí)的以A為起點(diǎn)的期望長度，F(xiàn)2[A]為A的右鄰邊走不到時(shí)的以A為起點(diǎn)的期望長度（本沙茶在代碼里全用F1表示了囧），這其中有相同的部分，就是A的兩條鄰邊都走不到時(shí)的期望長度，此時(shí)就是往A的樹內(nèi)走，按照樹的求法求即可，注意求F[A]時(shí)除的是(K+2)，F(xiàn)1[A]+F2[A]再把這個(gè)相同的部分減掉，就是以A為起點(diǎn)的期望長度了。然后，采用“扭根”操作可以求出以A樹中所有結(jié)點(diǎn)為起點(diǎn)的期望長度。枚舉環(huán)上的所有結(jié)點(diǎn)，按照上述辦法，就可以得到結(jié)果了。總時(shí)間復(fù)雜度為O(MN)，M為環(huán)上結(jié)點(diǎn)總數(shù)。
代碼：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 100010, INF = ~0U >> 2;
struct edge {
int a, b, w, pre, next;
bool mr;
} E0[(MAXN + 1) * 3], E[MAXN << 2];
int n, _n, m0, m, stk[MAXN], st[MAXN], pr[MAXN], pos_z, ts_len, TS[MAXN], Q[MAXN], pr1[MAXN], pr2[MAXN], lt[MAXN << 1], KS[MAXN];
bool loop_ex, vst[MAXN];
double F1[MAXN], F2[MAXN], res = 0;
void init_d0()
{
re(i, n) E0[i].pre = E0[i].next = i; if (n & 1) m0 = n + 1; else m0 = n;
}
void init_d()
{
re(i, n) E[i].pre = E[i].next = i; m = n;
}
void add_edge0(int a, int b, int w)
{
E0[m0].a = a; E0[m0].b = b; E0[m0].w = w; E0[m0].mr = 0; E0[m0].pre = E0[a].pre; E0[m0].next = a; E0[a].pre = m0; E0[E0[m0].pre].next = m0++;
E0[m0].a = b; E0[m0].b = a; E0[m0].w = w; E0[m0].mr = 0; E0[m0].pre = E0[b].pre; E0[m0].next = b; E0[b].pre = m0; E0[E0[m0].pre].next = m0++;
}
void del_edge0(int No)
{
E0[E0[No].pre].next = E0[No].next; E0[E0[No].next].pre = E0[No].pre;
E0[E0[No ^ 1].pre].next = E0[No ^ 1].next; E0[E0[No ^ 1].next].pre = E0[No ^ 1].pre;
}
void resu_edge0(int No)
{
E0[E0[No].pre].next = E0[E0[No].next].pre = No;
E0[E0[No ^ 1].pre].next = E0[E0[No ^ 1].next].pre = No ^ 1;
}
void add_edge(int a, int b, int w, bool mr)
{
E[m].a = a; E[m].b = b; E[m].w = w; E[m].mr = mr; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
}
void del_edge(int No)
{
E[E[No].pre].next = E[No].next; E[E[No].next].pre = E[No].pre;
}
void resu_edge(int No)
{
E[E[No].pre].next = E[E[No].next].pre = No;
}
void init()
{
int m00, a0, b0, w0;
scanf("%d%d", &n, &m00); loop_ex = m00 == n; init_d0();
re(i, m00) {
scanf("%d%d%d", &a0, &b0, &w0);
add_edge0(--a0, --b0, w0);
}
}
void prepare()
{
re(i, n) {st[i] = E0[i].next; vst[i] = 0;}
int x, y, tp = 0; bool FF; stk[0] = 0; vst[0] = 1; pos_z = pr[0] = -1;
while (tp >= 0) {
x = stk[tp]; FF = 0;
for (int p=st[x]; p != x; p=E0[p].next) {
y = E0[p].b;
if (!vst[y]) {
vst[y] = FF = 1; stk[++tp] = y; pr[y] = p; st[x] = E0[p].next; break;
} else if (p != (pr[x] ^ 1) && pos_z == -1) pos_z = p;
}
if (!FF) tp--;
}
x = E0[pos_z].a; y = E0[pos_z].b; E0[pos_z].mr = E0[pos_z ^ 1].mr = 1; ts_len = 0;
while (x != y) {TS[ts_len++] = x; E0[pr[x]].mr = E0[pr[x] ^ 1].mr = 1; x = E0[pr[x]].a;} TS[ts_len++] = y;
}
void mkt(int z)
{
init_d(); re(j, n) vst[j] = 0;
int x, y; Q[0] = z; vst[z] = 1;
for (int front=0, rear=0; front<=rear; front++) {
x = Q[front];
for (int p=E0[x].next; p != x; p=E0[p].next) {
y = E0[p].b;
if (!vst[y]) {
vst[y] = 1; Q[++rear] = y; pr1[y] = m; add_edge(x, y, E0[p].w, E0[p].mr);
}
}
}
}
void mkt2(int z)
{
init_d(); re(j, n) vst[j] = 0;
int x, y, front, rear; Q[0] = z; vst[z] = 1;
for (front=0, rear=0; front<=rear; front++) {
x = Q[front];
for (int p=E0[x].next; p != x; p=E0[p].next) if (!E0[p].mr) {
y = E0[p].b;
if (!vst[y]) {
vst[y] = 1; Q[++rear] = y; pr1[y] = m; add_edge(x, y, E0[p].w, 0);
}
}
}
_n = rear + 1;
}
void solve()
{
int x, y, z, sum, tp, lt_len; bool FF;
if (loop_ex) {
prepare();
re(i, ts_len) {
x = TS[i];
if (i == ts_len - 1) del_edge0(pos_z); else del_edge0(pr[x]);
mkt(x);
rre(j, n) {
y = Q[j]; if (E[y].next == y) {F1[y] = 0; continue;}
if (y == x) sum = 1; else sum = 0; F1[y] = 0;
for (int p=E[y].next; p != y; p=E[p].next) {
z = E[p].b; F1[y] += F1[z] + E[p].w; sum++;
}
F1[y] /= sum; KS[y] = sum;
}
res += F1[x];
re(j, n) {st[j] = E[j].next; vst[j] = 0;} lt_len = 0; stk[tp = 0] = x;
while (tp >= 0) {
y = stk[tp]; FF = 0;
for (int p=st[y]; p != y; p=E[p].next) if (!E[p].mr) {
z = E[p].b;
if (!vst[z]) {
vst[z] = FF = 1; stk[++tp] = z; lt[lt_len++] = z; break;
}
}
if (!FF) {lt[lt_len++] = -y - 1; tp--;}
}
if (lt_len == 1) lt_len = 0;
re(j, lt_len) {
y = lt[j];
if (y >= 0) {
z = E[pr1[y]].a; del_edge(pr1[y]); pr2[z] = m; add_edge(y, z, E[pr1[y]].w, 0);
if (E[z].next == z) {F1[z] = 0; KS[z] = 0;} else {F1[z] *= KS[z]--; F1[z] -= E[pr1[y]].w + F1[y]; F1[z] /= KS[z];}
if (E[y].next == y) {F1[y] = 0; KS[y] = 0;} else {F1[y] *= KS[y]++; F1[y] += E[pr1[y]].w + F1[z]; F1[y] /= KS[y];}
res += F1[y];
} else {
y = -y - 1;
z = E[pr1[y]].a; del_edge(pr2[z]); resu_edge(pr1[y]);
if (E[y].next == y) {F1[y] = 0; KS[y] = 0;} else {F1[y] *= KS[y]--; F1[y] -= E[pr2[z]].w + F1[z]; F1[y] /= KS[y];}
if (E[z].next == z) {F1[z] = 0; KS[z] = 0;} else {F1[z] *= KS[z]++; F1[z] += E[pr2[z]].w + F1[y]; F1[z] /= KS[z];}
}
}
if (i == ts_len - 1) resu_edge0(pos_z); else resu_edge0(pr[x]);
if (!i) del_edge0(pos_z); else del_edge0(pr[TS[i - 1]]);
mkt(x);
rre(j, n) {
y = Q[j]; if (E[y].next == y) {F1[y] = 0; continue;}
if (y == x) sum = 1; else sum = 0; F1[y] = 0;
for (int p=E[y].next; p != y; p=E[p].next) {
z = E[p].b; F1[y] += F1[z] + E[p].w; sum++;
}
F1[y] /= sum; KS[y] = sum;
}
res += F1[x];
re(j, n) {st[j] = E[j].next; vst[j] = 0;} lt_len = 0; stk[tp = 0] = x;
while (tp >= 0) {
y = stk[tp]; FF = 0;
for (int p=st[y]; p != y; p=E[p].next) if (!E[p].mr) {
z = E[p].b;
if (!vst[z]) {
vst[z] = FF = 1; stk[++tp] = z; lt[lt_len++] = z; break;
}
}
if (!FF) {lt[lt_len++] = -y - 1; tp--;}
}
if (lt_len == 1) lt_len = 0;
re(j, lt_len) {
y = lt[j];
if (y >= 0) {
z = E[pr1[y]].a; del_edge(pr1[y]); pr2[z] = m; add_edge(y, z, E[pr1[y]].w, 0);
if (E[z].next == z) {F1[z] = 0; KS[z] = 0;} else {F1[z] *= KS[z]--; F1[z] -= E[pr1[y]].w + F1[y]; F1[z] /= KS[z];}
if (E[y].next == y) {F1[y] = 0; KS[y] = 0;} else {F1[y] *= KS[y]++; F1[y] += E[pr1[y]].w + F1[z]; F1[y] /= KS[y];}
res += F1[y];
} else {
y = -y - 1;
z = E[pr1[y]].a; del_edge(pr2[z]); resu_edge(pr1[y]);
if (E[y].next == y) {F1[y] = 0; KS[y] = 0;} else {F1[y] *= KS[y]--; F1[y] -= E[pr2[z]].w + F1[z]; F1[y] /= KS[y];}
if (E[z].next == z) {F1[z] = 0; KS[z] = 0;} else {F1[z] *= KS[z]++; F1[z] += E[pr2[z]].w + F1[y]; F1[z] /= KS[z];}
}
}
if (!i) resu_edge0(pos_z); else resu_edge0(pr[TS[i - 1]]);
mkt2(x);
rre(j, _n) {
y = Q[j]; if (E[y].next == y) {F1[y] = 0; continue;}
if (y == x) sum = 2; else sum = 0; F1[y] = 0;
for (int p=E[y].next; p != y; p=E[p].next) {
z = E[p].b; F1[y] += F1[z] + E[p].w; sum++;
}
F1[y] /= sum; KS[y] = sum;
}
res -= F1[x];
re(j, n) {st[j] = E[j].next; vst[j] = 0;} lt_len = 0; stk[tp = 0] = x;
while (tp >= 0) {
y = stk[tp]; FF = 0;
for (int p=st[y]; p != y; p=E[p].next) {
z = E[p].b;
if (!vst[z]) {
vst[z] = FF = 1; stk[++tp] = z; lt[lt_len++] = z; break;
}
}
if (!FF) {lt[lt_len++] = -y - 1; tp--;}
}
if (lt_len == 1) lt_len = 0;
re(j, lt_len) {
y = lt[j];
if (y >= 0) {
z = E[pr1[y]].a; del_edge(pr1[y]); pr2[z] = m; add_edge(y, z, E[pr1[y]].w, 0);
if (E[z].next == z) {F1[z] = 0; KS[z] = 0;} else {F1[z] *= KS[z]--; F1[z] -= E[pr1[y]].w + F1[y]; F1[z] /= KS[z];}
if (E[y].next == y) {F1[y] = 0; KS[y] = 0;} else {F1[y] *= KS[y]++; F1[y] += E[pr1[y]].w + F1[z]; F1[y] /= KS[y];}
res -= F1[y];
} else {
y = -y - 1;
z = E[pr1[y]].a; del_edge(pr2[z]); resu_edge(pr1[y]);
if (E[y].next == y) {F1[y] = 0; KS[y] = 0;} else {F1[y] *= KS[y]--; F1[y] -= E[pr2[z]].w + F1[z]; F1[y] /= KS[y];}
if (E[z].next == z) {F1[z] = 0; KS[z] = 0;} else {F1[z] *= KS[z]++; F1[z] += E[pr2[z]].w + F1[y]; F1[z] /= KS[z];}
}
}
}
} else {
mkt(0);
rre(i, n) {
y = Q[i]; if (E[y].next == y) {F1[y] = 0; continue;}
sum = 0; F1[y] = 0;
for (int p=E[y].next; p != y; p=E[p].next) {
z = E[p].b; F1[y] += F1[z] + E[p].w; sum++;
}
F1[y] /= sum; KS[y] = sum;
}
res += F1[0];
re(i, n) {st[i] = E[i].next; vst[i] = 0;} lt_len = 0; stk[tp = 0] = 0;
while (tp >= 0) {
y = stk[tp]; FF = 0;
for (int p=st[y]; p != y; p=E[p].next) if (!E[p].mr) {
z = E[p].b;
if (!vst[z]) {
vst[z] = FF = 1; stk[++tp] = z; lt[lt_len++] = z; break;
}
}
if (!FF) {lt[lt_len++] = -y - 1; tp--;}
}
re(i, lt_len) {
y = lt[i];
if (y >= 0) {
z = E[pr1[y]].a; del_edge(pr1[y]); pr2[z] = m; add_edge(y, z, E[pr1[y]].w, 0);
if (E[z].next == z) {F1[z] = 0; KS[z] = 0;} else {F1[z] *= KS[z]--; F1[z] -= E[pr1[y]].w + F1[y]; F1[z] /= KS[z];}
if (E[y].next == y) {F1[y] = 0; KS[y] = 0;} else {F1[y] *= KS[y]++; F1[y] += E[pr1[y]].w + F1[z]; F1[y] /= KS[y];}
res += F1[y];
} else {
y = -y - 1;
z = E[pr1[y]].a; del_edge(pr2[z]); resu_edge(pr1[y]);
if (E[y].next == y) {F1[y] = 0; KS[y] = 0;} else {F1[y] *= KS[y]--; F1[y] -= E[pr2[z]].w + F1[z]; F1[y] /= KS[y];}
if (E[z].next == z) {F1[z] = 0; KS[z] = 0;} else {F1[z] *= KS[z]++; F1[z] += E[pr2[z]].w + F1[y]; F1[z] /= KS[z];}
}
}
}
res /= n;
}
void pri()
{
printf("%.5lf\n", res);
}
int main()
{
init();
solve();
pri();
return 0;
}