Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include<algorithm>
- #include<iostream>
- #include<cmath>
- #include<string>
- #include<vector>
- using namespace std;
- const int MAX_N = 50100;
- const int MAX_M = 75100;
- vector <pair<int, int> > g[MAX_N], h[MAX_N], q;
- int flag[MAX_N];
- int parent[MAX_N];
- int sz[MAX_N];
- int ancestor[MAX_N];
- int ans[MAX_M];
- int dp[MAX_N];
- int find_set(int v)
- {
- if (v == parent[v])
- return v;
- parent[v] = find_set(parent[v]);
- return parent[v];
- }
- void make_set(int a, int b)
- {
- a = find_set(a);
- b = find_set(b);
- if (sz[b]>sz[a])
- swap(a, b);
- sz[a] += sz[b];
- parent[b] = a;
- }
- void dfs(int v, int s)
- {
- flag[v] = 1;
- dp[v] = s;
- ancestor[find_set(v)] = v;
- for (int i = 0; i<g[v].size(); i++)
- {
- if (flag[g[v][i].first] == 0)
- {
- dfs(g[v][i].first, s + g[v][i].second);
- make_set(v, g[v][i].first);
- ancestor[find_set(v)] = v;
- }
- }
- flag[v] = 2;
- for (int i = 0; i<h[v].size(); i++)
- {
- if (flag[h[v][i].first] == 2)
- ans[h[v][i].second] = ancestor[find_set(h[v][i].first)];
- }
- }
- int main()
- {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int n, m, a, b, c;
- cin >> n;
- for (int i = 1; i<n; i++)
- {
- cin >> a >> b >> c;
- g[a].push_back(make_pair(b, c));
- g[b].push_back(make_pair(a, c));
- }
- for (int i = 0; i<n; i++)
- {
- sz[i] = 1;
- parent[i] = i;
- flag[i] = 0;
- }
- cin >> m;
- for (int i = 0; i<m; i++)
- {
- cin >> a >> b;
- h[a].push_back(make_pair(b, i));
- h[b].push_back(make_pair(a, i));
- q.push_back(make_pair(a, b));
- }
- dfs(0, 0);
- for (int i = 0; i<m; i++)
- {
- a = q[i].first;
- b = q[i].second;
- c = ans[i];
- cout<< dp[a] + dp[b] - 2 * dp[c] <<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement