Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2014
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.82 KB | None | 0 0
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <cassert>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <ctime>
  8. #include <deque>
  9. #include <functional>
  10. #include <iomanip>
  11. #include <iostream>
  12. #include <map>
  13. #include <numeric>
  14. #include <queue>
  15. #include <set>
  16. #include <sstream>
  17. #include <string>
  18. #include <vector>
  19.  
  20. #include <unistd.h>
  21.  
  22. #define DEBUG(z, x) { cerr << setw(z) << "" << (#x) << " = " << (x) << '\n'; }
  23.  
  24. using namespace std;
  25.  
  26. const int N = 500010;
  27. const int Q = 100010;
  28. const long long INF = 0x3C3C3C3C3C3C3C3CLL;
  29.  
  30. struct edge {
  31.   int to, dist;
  32.   edge(int to, int dist) : to(to), dist(dist) { }
  33. };
  34.  
  35. vector<edge> graph[N];
  36. vector<int> query[N];
  37. bool visit[N], mark[N];
  38. int total, sub[N], q[N], clear[Q << 1];
  39. long long dist[N], ans[Q << 1], bst[Q << 1];
  40.  
  41. void dfs_sz(int u, int p) {
  42.   sub[u] = 1;
  43.   for (int i = 0; i < graph[u].size(); ++i) {
  44.     int v = graph[u][i].to;    
  45.     if (!mark[v]) {
  46.       if (v != p) {    
  47.         dfs_sz(v, u);
  48.         sub[u] += sub[v];
  49.       }
  50.     } else {
  51.       swap(graph[u][i], graph[u].back());
  52.       graph[u].pop_back();
  53.       --i;
  54.     }
  55.   }
  56. }
  57.  
  58. int dfs_center(int u, int p) {
  59.   int heavy = N - 1;
  60.   for (int i = 0; i < graph[u].size(); ++i) {
  61.     int v = graph[u][i].to;
  62.     if (v != p && sub[v] > sub[heavy]) {
  63.       heavy = v;
  64.     }
  65.   }
  66.   if (sub[heavy] << 1 <= total) return u;
  67.   return dfs_center(heavy, u);
  68. }
  69.  
  70. void solve(int root) {
  71.   dfs_sz(root, -1);
  72.   total = sub[root];
  73.   int ct = dfs_center(root, -1);
  74.   dist[ct] = 0;
  75.   int sz = graph[ct].size();
  76.   bool f = !visit[ct];
  77.   visit[ct] = f;
  78.   int s = 0;
  79.   for (int i = 0; i < query[ct].size(); ++i) {
  80.     int id = query[ct][i];
  81.     if (bst[id ^ 1] == 0) ans[id] = 0;
  82.     bst[id] = 0;
  83.     clear[s++] = id;
  84.   }
  85.   for (int i = 0; i < sz; ++i) {
  86.     int u = graph[ct][i].to;
  87.     dist[u] = graph[ct][i].dist;
  88.     int tail = 0;
  89.     q[tail++] = u;
  90.     visit[u] = f;
  91.     for (int head = 0; head < tail; ++head) {
  92.       int v = q[head];
  93.       for (int j = 0; j < query[v].size(); ++j) {
  94.         int id = query[v][j];
  95.         if (bst[id ^ 1] < INF) {
  96.           ans[id] = min(ans[id], bst[id ^ 1] + dist[v]);
  97.         }
  98.       }
  99.       for (int j = 0; j < graph[v].size(); ++j) {
  100.         int z = graph[v][j].to;
  101.         if (visit[z] != f) {
  102.           visit[z] = f;
  103.           dist[z] = dist[v] + graph[v][j].dist;
  104.           q[tail++] = z;
  105.         }
  106.       }
  107.     }
  108.     if (i < sz - 1) {
  109.       for (int j = 0; j < tail; ++j) {
  110.         int u = q[j];
  111.         for (int j = 0; j < query[u].size(); ++j) {
  112.           int id = query[u][j];
  113.           if (bst[id] == INF) clear[s++] = id, bst[id] = dist[u];
  114.           else bst[id] = min(bst[id], dist[u]);
  115.         }
  116.       }
  117.     }
  118.   }
  119.   for (int i = 0; i < s; ++i) {
  120.     bst[clear[i]] = INF;
  121.   }
  122.   mark[ct] = 1;
  123.   for (int i = 0; i < sz; ++i) {
  124.     solve(graph[ct][i].to);
  125.   }
  126. }
  127.  
  128. int main() {
  129.   //assert(freopen("input.txt", "r", stdin));
  130.   //assert(freopen("output.txt", "w", stdout));
  131.   std::ios::sync_with_stdio(0);
  132.   std::cin.tie(0);
  133.   int n, q;
  134.   cin >> n >> q;
  135.   for (int i = 1; i < n; ++i) {
  136.     int u, v, c;
  137.     cin >> u >> v >> c;
  138.     graph[u].push_back(edge(v, c));
  139.     graph[v].push_back(edge(u, c));
  140.   }
  141.   for (int i = 1; i <= q; ++i) {
  142.     int a, b, u;
  143.     cin >> a >> b;
  144.     for (int j = 0; j < a; ++j) {
  145.       cin >> u;
  146.       query[u].push_back(i << 1);
  147.     }
  148.     for (int j = 0; j < b; ++j) {
  149.       cin >> u;
  150.       query[u].push_back(i << 1 | 1);
  151.     }
  152.   }
  153.   for (int i = 0; i < n; ++i) {
  154.     sort(query[i].begin(), query[i].end());
  155.     query[i].erase(unique(query[i].begin(), query[i].end()), query[i].end());
  156.   }
  157.   memset(ans, 0x3C, sizeof(ans));
  158.   memset(bst, 0x3C, sizeof(bst));
  159.   solve(0);
  160.   for (int i = 1; i <= q; ++i) {
  161.     cout << min(ans[i << 1], ans[i << 1 | 1]) << '\n';
  162.   }
  163. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement