#include #include #include #include #include #include #include using namespace std; struct Edge { int to; int weight; }; // Conjugate Gradient method vector conjugate_gradient(const vector>& A, const vector& b) { int n = A.size(); vector x(n, 0.0); vector r = b; vector p = r; double rsold = inner_product(r.begin(), r.end(), r.begin(), 0.0); for (int i = 0; i < n; ++i) { vector Ap(n, 0.0); for (int j = 0; j < n; ++j) { for (int k = 0; k < n; ++k) { Ap[j] += A[j][k] * p[k]; } } double alpha = rsold / inner_product(p.begin(), p.end(), Ap.begin(), 0.0); for (int j = 0; j < n; ++j) { x[j] += alpha * p[j]; r[j] -= alpha * Ap[j]; } double rsnew = inner_product(r.begin(), r.end(), r.begin(), 0.0); p = vector(n, 0.0); for(int j = 0; j < n; ++j){ p[j] = r[j] + (rsnew / rsold) * p[j]; } rsold = rsnew; } return x; } int main() { ifstream inFile("bochi.in"); ofstream outFile("bochi.out"); if (!inFile.is_open()) { cerr << "Error opening input file!" << endl; return 1; } if (!outFile.is_open()) { cerr << "Error opening output file!" << endl; inFile.close(); return 1; } int n, m; inFile >> n >> m; vector> adj(n + 1); for (int i = 0; i < n - 1; ++i) { int a, b, c; inFile >> a >> b >> c; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } for (int i = 0; i < m; ++i) { int start, end; inFile >> start >> end; vector expected_moves(n + 1, 0.0); expected_moves[end] = 0.0; vector visited(n + 1, false); queue q; q.push(start); visited[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); if (u == end) continue; double total_weight = 0; for (const Edge& edge : adj[u]) { total_weight += edge.weight; } for (const Edge& edge : adj[u]) { int v = edge.to; if (!visited[v]) { q.push(v); visited[v] = true; } } } vector reachable_nodes; for (int j = 1; j <= n; ++j) { if (visited[j]) { reachable_nodes.push_back(j); } } int num_reachable = reachable_nodes.size(); vector b(num_reachable, 0.0); vector> A(num_reachable, vector(num_reachable, 0.0)); vector node_index_map(n + 1, -1); for (int j = 0; j < num_reachable; ++j) { node_index_map[reachable_nodes[j]] = j; } for (int u : reachable_nodes) { if (u == end) { A[node_index_map[u]][node_index_map[u]] = 1.0; continue; } A[node_index_map[u]][node_index_map[u]] = 1.0; b[node_index_map[u]] = 1.0; double total_weight = 0; for (const Edge& edge : adj[u]) { total_weight += edge.weight; } for (const Edge& edge : adj[u]) { if (visited[edge.to]) { A[node_index_map[u]][node_index_map[edge.to]] = -(double)edge.weight / total_weight; } } } vector x = conjugate_gradient(A, b); for (int j = 0; j < num_reachable; ++j) { expected_moves[reachable_nodes[j]] = x[j]; } outFile << fixed << setprecision(2) << expected_moves[start] << endl; } inFile.close(); outFile.close(); return 0; }