| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1231088 | lmquan | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
#include "factories.h"
#define taskname ""
#include <bits/stdc++.h>
using namespace std;
const int kN = 500005;
const int kLG = 20;
const long long kInf = 91632847297843575;
vector<pair<int, int>> children[kN];
int in[kN], out[kN], jump[kLG][kN], timer, w[kN];
bool markX[kN], markY[kN];
long long p[kN], dp[2][kN];
vector<pair<int, long long>> vt[kN];
void DFS(int u, int v) {
in[u] = ++timer;
jump[0][u] = v;
for (int i = 1; i < kLG; i++) {
jump[i][u] = jump[i - 1][jump[i - 1][u]];
}
for (auto i : children[u]) {
if (i.first == v) {
continue;
}
DFS(i.first, u);
w[i.first] = i.second;
}
out[u] = timer;
}
bool Ancestor(int u, int v) {
return (in[v] <= in[u] && out[u] <= out[v]);
}
int LCA(int u, int v) {
if (Ancestor(u, v)) {
return v;
}
for (int i = kLG - 1; i >= 0; i--) {
if (jump[i][v] != -1 && !Ancestor(u, jump[i][v])) {
v = jump[i][v];
}
}
return jump[0][v];
}
bool DFSTimer(int u, int v) {
return in[u] < in[v];
}
long long SumPath(int x, int y) {
return p[y] + p[x] - 2 * p[LCA(x, y)];
}
void Init(int N, int A[], int B[], int D[]) {
memset(jump, -1, sizeof(jump));
for (int i = 0; i < N - 1; i++) {
children[A[i]].push_back(make_pair(B[i], D[i]));
children[B[i]].push_back(make_pair(A[i], D[i]));
}
int root = 0;
DFS(root, root);
for (int i = 1; i < N; i++) {
p[i] = p[jump[0][i]] + w[i];
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < 2; j++) {
dp[j][i] = kInf;
}
}
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> u;
for (int i = 0; i < S; i++) {
markX[X[i]] = true;
u.push_back(X[i]);
}
for (int i = 0; i < T; i++) {
markY[Y[i]] = true;
u.push_back(Y[i]);
}
sort(u.begin(), u.end(), DFSTimer);
int l = u.size() - 1;
for (int i = 0; i < l; i++) {
u.push_back(LCA(u[i], u[i + 1]));
}
sort(u.begin(), u.end(), DFSTimer);
u.erase(unique(u.begin(), u.end()), u.end());
stack<int> st;
st.push(u[0]);
for (int i = 1; i < u.size(); i++) {
while (!st.empty() && !Ancestor(u[i], st.top())) {
st.pop();
}
vt[st.top()].push_back(make_pair(u[i], SumPath(st.top(), u[i])));
st.push(u[i]);
}
function<void(int i)> CalculateDP = [&](int i) {
if (markX[i]) {
dp[0][i] = 0;
}
if (markY[i]) {
dp[1][i] = 0;
}
for (auto j : vt[i]) {
CalculateDP(j.first);
if (dp[0][j.first] != kInf) {
dp[0][i] = min(dp[0][i], dp[0][j.first] + j.second);
}
if (dp[1][j.first] != kInf) {
dp[1][i] = min(dp[1][i], dp[1][j.first] + j.second);
}
}
};
CalculateDP(u[0]);
long long result = kInf;
for (int i : u) {
if (dp[0][i] != kInf && dp[1][i] != kInf) {
result = min(result, dp[0][i] + dp[1][i]);
}
}
for (int i : u) {
dp[0][i] = dp[1][i] = kInf;
vt[i].clear();
}
for (int i = 0; i < S; i++) {
markX[X[i]] = false;
}
for (int i = 0; i < T; i++) {
markY[Y[i]] = false;
}
return result;
}
int main() {
if (fopen(taskname".inp", "r")) {
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
int A[N], B[N], D[N];
for (int i = 0; i < N - 1; i++) {
cin >> A[i] >> B[i] >> D[i];
}
Init(N, A, B, D);
while (Q--) {
int S, T;
cin >> S >> T;
int X[S], Y[T];
for (int i = 0; i < S; i++) {
cin >> X[i];
}
for (int j = 0; j < T; j++) {
cin >> Y[j];
}
cout << Query(S, X, T, Y) << '\n';
}
return 0;
}