B.cc

/* |\ _,,,---,,_ /,`.-'`' -. ;-;;,_ |,4- ) )-,_..;\ ( `'-' '---''(_/--' `-'\_) Meow do you do ヽ(●´∀`●)ﾉ */ #include <iostream> #include <cstring> #include <cmath> #include <algorithm> #include <climits> #include <stack> #include <queue> #include <vector> #include <set> #include <map> #include <list> #define GET_BIT(n, i) (((n) & (1 << ((i)-1))) >> ((i)-1)) // i start from 1 #define SET_BIT(n, i) ((n) | (1 << ((i)-1))) #define CLR_BIT(n, i) ((n) & ~(1 << ((i)-1))) #define SHOW_A(x) {cout << #x << " = " << x << endl;} #define SHOW_B(x, y) {cout << #x << " = " << x << ", " << #y << " = " << y << endl;} #define SHOW_C(x, y, z) {cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;} #define REACH_HERE {cout << "REACH_HERE! line: " << __LINE__ << endl;} const double E = 1e-8; const double PI = acos(-1); using namespace std; struct Node { int parent; int to_parent; long long to_root; vector<int> children; vector<int> weight; vector<int> jump; int level; }; Node tree[50000]; int main() { ios::sync_with_stdio(false); int n; cin >> n; for (int i = 0; i < n-1; i++) { int x, y, w; cin >> x >> y >> w; tree[x].children.push_back(y); tree[y].children.push_back(x); tree[x].weight.push_back(w); tree[y].weight.push_back(w); } stack<int> s; s.push(0); tree[0].level = 1; // BFS while (s.size()) { int i = s.top(); s.pop(); for (int j = 0; j < tree[i].children.size(); j++) { if (tree[tree[i].children[j]].level == 0) { tree[tree[i].children[j]].parent = i; tree[tree[i].children[j]].to_parent = tree[i].weight[j]; tree[tree[i].children[j]].to_root = tree[i].to_root + tree[i].weight[j]; tree[tree[i].children[j]].jump.push_back(i); tree[tree[i].children[j]].level = tree[i].level + 1; s.push(tree[i].children[j]); } } } for (int j = 1; (1 << j) < n; j++) { for (int i = 0; i < n; i ++) { if (tree[i].jump.size() > j-1 && tree[tree[i].jump[j-1]].jump.size() > j-1) { tree[i].jump.push_back(tree[tree[i].jump[j-1]].jump[j-1]); } } } int q; cin >> q; for (int i = 0; i < q; i++) { int x, y; cin >> x >> y; if (tree[x].level < tree[y].level) { swap(x, y); } int ori_x = x, ori_y = y; // Go to same level int j = 0; while (tree[x].level != tree[y].level) { while (tree[x].jump.size() > j && tree[tree[x].jump[j]].level > tree[y].level) { j ++; } if (tree[x].jump.size() > j && tree[tree[x].jump[j]].level == tree[y].level) { x = tree[x].jump[j]; break; } x = tree[x].jump[j-1]; j = 0; } // Jump to the same node while (x != y) { j = 0; while (tree[x].jump.size() > j && tree[y].jump.size() > j && tree[x].jump[j] != tree[y].jump[j]) { j ++; } if (j == 0) j = 1; x = tree[x].jump[j-1]; y = tree[y].jump[j-1]; } long long dist = tree[ori_x].to_root + tree[ori_y].to_root - 2 * tree[x].to_root; cout << dist << endl; } return 0; }