Advertisement
Guest User

1471

a guest
Feb 22nd, 2018
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cmath>
  5. #include<string>
  6. #include<vector>
  7. using namespace std;
  8. const int MAX_N = 50100;
  9. const int MAX_M = 75100;
  10. vector <pair<int, int> > g[MAX_N], h[MAX_N], q;
  11. int flag[MAX_N];
  12. int parent[MAX_N];
  13. int sz[MAX_N];
  14. int ancestor[MAX_N];
  15. int ans[MAX_M];
  16. int dp[MAX_N];
  17. int find_set(int v)
  18. {
  19.     if (v == parent[v])
  20.         return v;
  21.     parent[v] = find_set(parent[v]);
  22.     return parent[v];
  23. }
  24. void make_set(int a, int b)
  25. {
  26.     a = find_set(a);
  27.     b = find_set(b);
  28.     if (sz[b]>sz[a])
  29.         swap(a, b);
  30.     sz[a] += sz[b];
  31.     parent[b] = a;
  32. }
  33. void dfs(int v, int s)
  34. {
  35.     flag[v] = 1;
  36.     dp[v] = s;
  37.     ancestor[find_set(v)] = v;
  38.     for (int i = 0; i<g[v].size(); i++)
  39.     {
  40.         if (flag[g[v][i].first] == 0)
  41.         {
  42.             dfs(g[v][i].first, s + g[v][i].second);
  43.             make_set(v, g[v][i].first);
  44.             ancestor[find_set(v)] = v;
  45.         }
  46.     }
  47.     flag[v] = 2;
  48.     for (int i = 0; i<h[v].size(); i++)
  49.     {
  50.         if (flag[h[v][i].first] == 2)
  51.             ans[h[v][i].second] = ancestor[find_set(h[v][i].first)];
  52.     }
  53. }
  54. int main()
  55. {
  56.     freopen("input.txt", "r", stdin);
  57.     freopen("output.txt", "w", stdout);
  58.     int n, m, a, b, c;
  59.     cin >> n;
  60.     for (int i = 1; i<n; i++)
  61.     {
  62.         cin >> a >> b >> c;
  63.         g[a].push_back(make_pair(b, c));
  64.         g[b].push_back(make_pair(a, c));
  65.     }
  66.     for (int i = 0; i<n; i++)
  67.     {
  68.         sz[i] = 1;
  69.         parent[i] = i;
  70.         flag[i] = 0;
  71.     }
  72.     cin >> m;
  73.     for (int i = 0; i<m; i++)
  74.     {
  75.         cin >> a >> b;
  76.         h[a].push_back(make_pair(b, i));
  77.         h[b].push_back(make_pair(a, i));
  78.         q.push_back(make_pair(a, b));
  79.     }
  80.     dfs(0, 0);
  81.     for (int i = 0; i<m; i++)
  82.     {
  83.         a = q[i].first;
  84.         b = q[i].second;
  85.         c = ans[i];
  86.         cout<< dp[a] + dp[b] - 2 * dp[c] <<endl;
  87.     }
  88.     return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement