Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #define FR(i, n) for(int i = 0; i < (n); i++)
- #define FOR(i, l, r) for(int i = (l); i < (r); i++)
- #define all(x) x.begin(), x.end()
- #define fs first
- #define sc second
- using namespace std;
- const int N = 5e4 + 10;
- int n, k;
- vector<pair<int, int>> g[N];
- int pr[N][17], gl[N], dist_0[N];
- void count_pr(int vx, int p1) {
- FR(i, 17) {
- pr[vx][i] = p1;
- p1 = pr[p1][i];
- }
- }
- void dfs_pr_lv(int vx, int lv, int p1, int dt) {
- gl[vx] = lv;
- dist_0[vx] = dt;
- count_pr(vx, p1);
- for(auto i : g[vx]) {
- if(gl[i.fs] == 0) {
- dfs_pr_lv(i.fs, lv+1, vx, dt + i.sc);
- }
- }
- }
- int find_vx(int va, int lv) {
- int k2 = 17;
- while(k2 != 0) {
- if(gl[pr[va][k2]] >= lv) {
- k2--;
- } else {
- va = pr[va][k2];
- }
- }
- return pr[va][0];
- }
- int lca(int bg, int ed) {
- if(gl[bg] > gl[ed]) swap(bg, ed);
- //cout << '(' << endl;
- ed = find_vx(ed, gl[bg]);
- //cout << bg << ' ' << ed << endl;
- if(bg == ed) return bg;
- int k2 = 17;
- while(k2 != 0) {
- if(pr[bg][k2] == pr[ed][k2]) {
- k2--;
- } else {
- bg = pr[bg][k2];
- ed = pr[ed][k2];
- }
- }
- return pr[bg][0];
- }
- int dist(int bg, int ed) {
- int cm_vx = lca(bg, ed);
- return dist_0[bg] + dist_0[ed] - 2 * dist_0[cm_vx];
- }
- signed main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- cin >> n;
- FR(i, n-1) {
- int a, b, c;
- cin >> a >> b >> c;
- g[a].push_back({b, c});
- g[b].push_back({a, c});
- }
- cin >> k;
- dfs_pr_lv(0, 1, 0, 0);
- FR(i, k) {
- int b, e;
- cin >> b >> e;
- cout << dist(b, e) << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement