Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <bitset>
- #include <cassert>
- #include <cmath>
- #include <cstdio>
- #include <cstring>
- #include <ctime>
- #include <deque>
- #include <functional>
- #include <iomanip>
- #include <iostream>
- #include <map>
- #include <numeric>
- #include <queue>
- #include <set>
- #include <sstream>
- #include <string>
- #include <vector>
- #include <unistd.h>
- #define DEBUG(z, x) { cerr << setw(z) << "" << (#x) << " = " << (x) << '\n'; }
- using namespace std;
- const int N = 500010;
- const int Q = 100010;
- const long long INF = 0x3C3C3C3C3C3C3C3CLL;
- struct edge {
- int to, dist;
- edge(int to, int dist) : to(to), dist(dist) { }
- };
- vector<edge> graph[N];
- vector<int> query[N];
- bool visit[N], mark[N];
- int total, sub[N], q[N], clear[Q << 1];
- long long dist[N], ans[Q << 1], bst[Q << 1];
- void dfs_sz(int u, int p) {
- sub[u] = 1;
- for (int i = 0; i < graph[u].size(); ++i) {
- int v = graph[u][i].to;
- if (!mark[v]) {
- if (v != p) {
- dfs_sz(v, u);
- sub[u] += sub[v];
- }
- } else {
- swap(graph[u][i], graph[u].back());
- graph[u].pop_back();
- --i;
- }
- }
- }
- int dfs_center(int u, int p) {
- int heavy = N - 1;
- for (int i = 0; i < graph[u].size(); ++i) {
- int v = graph[u][i].to;
- if (v != p && sub[v] > sub[heavy]) {
- heavy = v;
- }
- }
- if (sub[heavy] << 1 <= total) return u;
- return dfs_center(heavy, u);
- }
- void solve(int root) {
- dfs_sz(root, -1);
- total = sub[root];
- int ct = dfs_center(root, -1);
- dist[ct] = 0;
- int sz = graph[ct].size();
- bool f = !visit[ct];
- visit[ct] = f;
- int s = 0;
- for (int i = 0; i < query[ct].size(); ++i) {
- int id = query[ct][i];
- if (bst[id ^ 1] == 0) ans[id] = 0;
- bst[id] = 0;
- clear[s++] = id;
- }
- for (int i = 0; i < sz; ++i) {
- int u = graph[ct][i].to;
- dist[u] = graph[ct][i].dist;
- int tail = 0;
- q[tail++] = u;
- visit[u] = f;
- for (int head = 0; head < tail; ++head) {
- int v = q[head];
- for (int j = 0; j < query[v].size(); ++j) {
- int id = query[v][j];
- if (bst[id ^ 1] < INF) {
- ans[id] = min(ans[id], bst[id ^ 1] + dist[v]);
- }
- }
- for (int j = 0; j < graph[v].size(); ++j) {
- int z = graph[v][j].to;
- if (visit[z] != f) {
- visit[z] = f;
- dist[z] = dist[v] + graph[v][j].dist;
- q[tail++] = z;
- }
- }
- }
- if (i < sz - 1) {
- for (int j = 0; j < tail; ++j) {
- int u = q[j];
- for (int j = 0; j < query[u].size(); ++j) {
- int id = query[u][j];
- if (bst[id] == INF) clear[s++] = id, bst[id] = dist[u];
- else bst[id] = min(bst[id], dist[u]);
- }
- }
- }
- }
- for (int i = 0; i < s; ++i) {
- bst[clear[i]] = INF;
- }
- mark[ct] = 1;
- for (int i = 0; i < sz; ++i) {
- solve(graph[ct][i].to);
- }
- }
- int main() {
- //assert(freopen("input.txt", "r", stdin));
- //assert(freopen("output.txt", "w", stdout));
- std::ios::sync_with_stdio(0);
- std::cin.tie(0);
- int n, q;
- cin >> n >> q;
- for (int i = 1; i < n; ++i) {
- int u, v, c;
- cin >> u >> v >> c;
- graph[u].push_back(edge(v, c));
- graph[v].push_back(edge(u, c));
- }
- for (int i = 1; i <= q; ++i) {
- int a, b, u;
- cin >> a >> b;
- for (int j = 0; j < a; ++j) {
- cin >> u;
- query[u].push_back(i << 1);
- }
- for (int j = 0; j < b; ++j) {
- cin >> u;
- query[u].push_back(i << 1 | 1);
- }
- }
- for (int i = 0; i < n; ++i) {
- sort(query[i].begin(), query[i].end());
- query[i].erase(unique(query[i].begin(), query[i].end()), query[i].end());
- }
- memset(ans, 0x3C, sizeof(ans));
- memset(bst, 0x3C, sizeof(bst));
- solve(0);
- for (int i = 1; i <= q; ++i) {
- cout << min(ans[i << 1], ans[i << 1 | 1]) << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement