// we both did the best we could do, underneath the same moon, in different galaxies #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#define int long long typedef long long ll; typedef double ld; using namespace std; const int maxn = 2e5 + 5, logn = 19; vector > l(logn, vector(maxn, 0)); vector > up(logn, vector(maxn, 0)); // expected time until I go to my parent vector > dw(logn, vector(maxn, 0)); // if I'm in my parent, expected time until I go down vector here(maxn, 0); // if I'm here, expected time until I'll be here again int n, q; vector < vector > > g; vector d(maxn, 0); ld cnt(ld p) { return (1. / p - 1.) / (1. - p); } void dfs1(int u, int p = -1) { ld pr = 0.; for (pair v : g[u]) { if (v.first != p) { d[v.first] = d[u] + 1; l[0][v.first] = u; dfs1(v.first, u); up[0][u] += (up[0][v.first] + 1.) * v.second; } else pr = v.second; } if (p != -1) { if (g[u].size() > 1) up[0][u] *= cnt(pr); up[0][u] += 1.; } } void dfs2(int u, int p = -1) { ld sum = 0.; for (pair v : g[u]) { if (v.first != p) sum += (up[0][v.first] + 1.) * v.second; else sum += (dw[0][u] + 1.) * v.second; } for (pair v : g[u]) if (v.first != p) { dw[0][v.first] = sum - (up[0][v.first] + 1.) * v.second; if (g[u].size() > 1) dw[0][v.first] *= cnt(v.second); dw[0][v.first] += 1.; dfs2(v.first, u); } for (int j = 1; j < logn; j++) { l[j][u] = l[j - 1][l[j - 1][u]]; up[j][u] = up[j - 1][u] + up[j - 1][l[j - 1][u]]; dw[j][u] = dw[j - 1][u] + dw[j - 1][l[j - 1][u]]; } here[u] = 1.; for (pair v : g[u]) { if (v.first != p) here[u] += up[0][v.first] * v.second; else here[u] += dw[0][u] * v.second; } } int lca(int u, int v) { if (d[u] < d[v]) swap(u, v); for (int i = logn - 1; i >= 0; i--) if (d[l[i][u]] >= d[v]) u = l[i][u]; for (int i = logn - 1; i >= 0; i--) if (l[i][u] != l[i][v]) u = l[i][u], v = l[i][v]; return u == v ? u : l[0][u]; } ld query(int u, int v) { ld ans = here[v]; int w = lca(u, v); for (int i = logn - 1; i >= 0; i--) if (d[u] - (1 << i) >= d[w]) ans += up[i][u], u = l[i][u]; for (int i = logn - 1; i >= 0; i--) if (d[v] - (1 << i) >= d[w]) ans += dw[i][v], v = l[i][v]; return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); ifstream cin("bochi.in"); ofstream cout("bochi.out"); cin >> n >> q; g.assign(n, {}); for (int i = 0, u, v; i < n - 1; i++) { ld w; cin >> u >> v >> w; g[--u].push_back({ --v, w }); g[v].push_back({ u, w }); } for (int i = 0; i < n; i++) { ld sum = 0; for (pair p : g[i]) sum += p.second; for (pair& p : g[i]) p.second = p.second / sum; } dfs1(0); dfs2(0); cout << setprecision(2) << fixed; while (q--) { int a, b; cin >> a >> b; a--, b--; cout << query(a, b) << "\n"; } return 0; }