#include #include #include #include #include using namespace std; struct Edge { int to, w; }; const int MAXN = 200005; const int LOGN = 20; int N, M; vector adj[MAXN]; int S[MAXN]; // За всеки връх v: S(v) = сбор на тежестите на ребрата, минаващи през v long long totW = 0; // Общо тегло (сумата на всички ребра) // LCA структура int parent[MAXN][LOGN]; int depth[MAXN]; void dfsLCA(int v, int p, int d) { depth[v] = d; parent[v][0] = p; for (auto& e : adj[v]) { if (e.to == p) continue; dfsLCA(e.to, v, d + 1); } } int LCA(int a, int b) { if (depth[a] < depth[b]) swap(a, b); int diff = depth[a] - depth[b]; for (int i = 0; i < LOGN; i++) { if (diff & (1 << i)) a = parent[a][i]; } if (a == b) return a; for (int i = LOGN - 1; i >= 0; i--) { if (parent[a][i] != parent[b][i]) { a = parent[a][i]; b = parent[b][i]; } } return parent[a][0]; } double F[MAXN]; // Първият DFS – “надолу” по дървото void dfs1(int v, int p) { F[v] = 0.0; for (auto &e : adj[v]) { if(e.to == p) continue; dfs1(e.to, v); F[v] += ((double)e.w / S[v]) * (F[e.to] + 1.0); } } // Вторият DFS – преизчисляване при преориентиране (от родител към дете) void dfs2(int v, int p) { for (auto& e : adj[v]) { if (e.to == p) continue; double prev = F[e.to]; F[e.to] += (F[v] - (F[e.to] + 1.0)) * ((double)e.w / S[e.to]); dfs2(e.to, v); } } // Коригираната функция за изчисляване на очаквания брой ходове – тук се въвежда поправката за 50% шанс при b. double calcExpected(int a, int b) { // Формулата става: // E(a) = (F[a] - F[b]) + (2 + Σ[за всеки ребро (b,u)] (e.w/S[b])*(F[u] - F[b]) ) double correction = 50.0; for (auto& e : adj[b]) { correction += ((double)e.w / S[b]) * (F[e.to] - F[b]); } return (F[a] - F[b]) + correction; } int main() { ifstream inp("bochi.in"); inp >> N >> M; for (int i = 1; i <= N; i++) { S[i] = 0; } for (int i = 1; i <= N - 1; i++) { int u, v, w; inp >> u >> v >> w; adj[u].push_back({ v, w }); adj[v].push_back({ u, w }); totW += w; S[u] += w; S[v] += w; } dfsLCA(1, 0, 0); for (int j = 1; j < LOGN; j++) { for (int i = 1; i <= N; i++) { if (parent[i][j - 1] != 0) parent[i][j] = parent[parent[i][j - 1]][j - 1]; else parent[i][j] = 0; } } // Изчисляване на потенциалната функция F върху дървото с два DFS – първо надолу, после преориентиране dfs1(1, 0); dfs2(1, 0); ofstream out("bochi.out"); out << fixed << setprecision(6); for (int i = 0; i < M; i++) { int a, b; inp >> a >> b; double ans = calcExpected(a, b); out << ans << "\n"; } inp.close(); out.close(); return 0; }