Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Make CSP great again
- //Vengeance
- #include <bits/stdc++.h>
- #define TASK "TESTCODE"
- #define Log2(x) 31 - __builtin_clz(x)
- using namespace std;
- const int N = 1e5 , cbit = 16;
- int f[N + 1][cbit + 1], depth[N + 1], l[N + 1], r[N + 1], w[N + 1], sz[N + 1], par[N + 1], timer, n, s, q, e;
- long long g[N + 1];
- bool visited[N + 1];
- set<pair<long long, int> > dp[N + 1];
- vector<int> adj[N + 1];
- void read()
- {
- cin >> n >> s >> q >> e;
- for (int i = 1; i < n; ++ i)
- {
- cin >> l[i] >> r[i] >> w[i];
- adj[l[i]].push_back(i);
- adj[r[i]].push_back(i);
- }
- }
- void DFS(int u, int p)
- {
- for (int x: adj[u])
- {
- int v = l[x] ^ r[x] ^ u;
- if (v == p)
- {
- continue;
- }
- depth[v] = depth[u] + 1;
- g[v] = g[u] + w[x];
- f[v][0] = u;
- for (int i = 1; i <= cbit; ++ i)
- {
- f[v][i] = f[f[v][i - 1]][i - 1];
- }
- DFS(v, u);
- }
- }
- int LCA(int u, int v)
- {
- if (depth[v] < depth[u])
- {
- swap(u, v);
- }
- int k = depth[v] - depth[u];
- for (int i = cbit; i >= 0; -- i)
- {
- if ((k >> i) & 1)
- {
- v = f[v][i];
- }
- }
- if (u == v)
- {
- return u;
- }
- for (int i = cbit; i >= 0; -- i)
- {
- if (f[u][i] != f[v][i])
- {
- u = f[u][i];
- v = f[v][i];
- }
- }
- return f[u][0];
- }
- long long dis(int u, int v)
- {
- int k = LCA(u, v);
- return g[u] + g[v] - 2 * g[k];
- }
- void CenDFS(int u, int p)
- {
- sz[u] = 1;
- for (int x : adj[u])
- {
- int v = l[x] ^ r[x] ^ u;
- if (v == p || visited[v])
- {
- continue;
- }
- CenDFS(v, u);
- sz[u] += sz[v];
- }
- }
- int FindCentroid(int u, int p, int s)
- {
- for (int x : adj[u])
- {
- int v = l[x] ^ r[x] ^ u;
- if (v == p || visited[v])
- {
- continue;
- }
- if (sz[v] > s/2)
- {
- return FindCentroid(v, u, s);
- }
- }
- return u;
- }
- int BuildCentroid(int u)
- {
- CenDFS(u, 0);
- int root = FindCentroid(u, 0, sz[u]);
- visited[root] = true;
- for (int x : adj[root])
- {
- int v = l[x] ^ r[x] ^ root;
- if (visited[v])
- {
- continue;
- }
- par[BuildCentroid(v)] = root;
- }
- return root;
- }
- void update(int u)
- {
- for (int v = u; v > 0; v = par[v])
- {
- dp[v].insert({dis(u, v), u});
- }
- }
- int nchain = 1, chain[N + 1], pos[N + 1], head[N + 1];
- void preHLD(int u, int p)
- {
- sz[u] = 1;
- for (int x : adj[u])
- {
- int v = l[x] ^ r[x] ^ u;
- if (v == p)
- {
- continue;
- }
- preHLD(v, u);
- sz[u] += sz[v];
- }
- }
- struct FenwickTree
- {
- int tree[N + 1];
- void add(int pos, int val)
- {
- for (; pos <= n; pos += (pos & (-pos)))
- {
- tree[pos] += val;
- }
- }
- int sum(int pos)
- {
- int ret = 0;
- for (; pos > 0; pos -= (pos & (-pos)))
- {
- ret += tree[pos];
- }
- return ret;
- }
- int sum(int l, int r)
- {
- if (l > r)
- {
- return 0;
- }
- return sum(r) - sum(l - 1);
- }
- } tree;
- void HLD(int u, int p)
- {
- int bigchild = -1;
- chain[u] = nchain;
- pos[u] = ++timer;
- if (head[nchain] == 0)
- {
- head[nchain] = u;
- }
- for (int x : adj[u])
- {
- int v = l[x] ^ r[x] ^ u;
- if (v == p)
- {
- continue;
- }
- if (bigchild == -1 || sz[bigchild] < sz[v])
- {
- bigchild = v;
- }
- }
- if (bigchild != -1)
- {
- HLD(bigchild, u);
- }
- for (int x : adj[u])
- {
- int v = l[x] ^ r[x] ^ u;
- if (v == bigchild || v == p)
- {
- continue;
- }
- ++nchain;
- HLD(v, u);
- }
- }
- bool reachable(int u, int p)
- {
- while(chain[u] != chain[p])
- {
- if (tree.sum(pos[head[chain[u]]], pos[u]) > 0)
- {
- return false;
- }
- u = f[head[chain[u]]][0];
- }
- return tree.sum(pos[p] + 1, pos[u]) == 0;
- }
- bool reach(int u, int v)
- {
- int k = LCA(u, v);
- return reachable(u, k) && reachable(v, k);
- }
- int get(int u)
- {
- long long res = -1;
- for (int v = u; v > 0; v = par[v])
- {
- while(!dp[v].empty() && !reach(dp[v].begin()->second, v))
- {
- dp[v].erase(dp[v].begin());
- }
- if (reach(u, v) && !dp[v].empty())
- {
- if (res == -1 || res > dp[v].begin()->first + dis(u, v))
- {
- res = dp[v].begin()->first + dis(u, v);
- }
- }
- }
- return res;
- }
- void prepare()
- {
- DFS(1, 0);
- par[BuildCentroid(1)] = 0;
- timer = 0;
- preHLD(1, 0);
- HLD(1, 0);
- for (int i = 1; i <= s; ++ i)
- {
- int u;
- cin >> u;
- update(u);
- }
- fill(visited + 1, visited + n, false);
- }
- void solve()
- {
- prepare();
- while(q--)
- {
- int i, u;
- cin >> i >> u;
- if (!visited[i])
- {
- visited[i] = true;
- if (depth[l[i]] > depth[r[i]])
- {
- swap(l[i], r[i]);
- }
- tree.add(pos[r[i]], 1);
- }
- if (reach(u, e))
- {
- cout << "escaped" << '\n';
- continue;
- }
- long long res = get(u);
- if (res == -1)
- {
- cout << "oo" << '\n';
- }
- else
- {
- cout << res << '\n';
- }
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- if (fopen(TASK".INP", "r"))
- {
- freopen(TASK".INP", "r", stdin);
- //freopen(TASK".OUT", "w", stdout);
- }
- int t = 1;
- bool typetest = false;
- if (typetest)
- {
- cin >> t;
- }
- for (int __ = 1; __ <= t; ++ __)
- {
- //cout << "Case " << __ << ": ";
- read();
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement