| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 779953 | vjudge1 | Factories (JOI14_factories) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
const int NM = 5e5, LOG = 18, inf = 1e18;
struct edge{
int u, v, c;
edge(int a, int b, int w){
u = a, v = b, c = w;
}
};
int T = 1, N, Q, parent[NM+5], h[NM+5], jump[NM+5][LOG+5], d[NM+5][LOG+5];
vector <pii> adj[NM+5];
int t, s[NM+5], e[NM+5];
vector <int> L, L1;
int col[NM+5];
stack <int> st;
vector <pii> son[NM+5];
int dp1[NM+5], dp2[NM+5], ans;
void DFS(int u){
s[u] = ++t;
for (int i = 0; i < adj[u].size(); i++){
int v = adj[u][i].fi;
if (h[v] != -1) continue;
parent[v] = u;
h[v] = h[u]+1;
d[v][0] = adj[u][i].se;
DFS(v);
}
e[u] = t;
}
void build(){
d[0][0] = -1;
for (int i = 1; i <= N; i++)
jump[i][0] = parent[i];
for (int j = 1; j <= LOG; j++)
for (int i = 1; i <= N; i++)
if (jump[i][j-1] != -1){
jump[i][j] = jump[jump[i][j-1]][j-1];
d[i][j] = d[i][j-1]+d[jump[i][j-1]][j-1];
}
else{
jump[i][j] = -1;
d[i][j] = -1;
}
}
bool is_ancestor(int a, int u){
return s[a] <= s[u] && e[a] >= e[u];
}
int LCA(int u, int v){
if (h[u] < h[v]) swap(u, v);
for (int i = LOG; i >= 0; i--)
if (h[u]-(1<<i) >= h[v]) u = jump[u][i];
if (u == v) return u;
for (int i = LOG; i >= 0; i--)
if (jump[u][i] != -1 && jump[u][i] != jump[v][i]){
u = jump[u][i];
v = jump[v][i];
}
return parent[u];
}
int get(int a, int u){
int res = 0;
for (int i = LOG; i >= 0; i--)
if (h[u]-(1<<i) >= h[a]){
res += d[u][i];
u = jump[u][i];
}
return res;
}
bool cmp(int x, int y){
return s[x] < s[y];
}
void DFS2(int u){
dp1[u] = +inf, dp2[u] = +inf;
for (int i = 0; i < son[u].size(); i++){
int v = son[u][i].fi;
DFS2(v);
ans = min(ans, dp1[u]+dp2[v]+son[u][i].se);
ans = min(ans, dp2[u]+dp1[v]+son[u][i].se);
dp1[u] = min(dp1[u], dp1[v]+son[u][i].se);
dp2[u] = min(dp2[u], dp2[v]+son[u][i].se);
}
if (col[u] == 1){
dp1[u] = 0;
ans = min(ans, dp2[u]);
}
if (col[u] == 2){
dp2[u] = 0;
ans = min(ans, dp1[u]);
}
}
void solve_query(){
sort(L.begin(), L.end(), cmp);
L1.clear();
for (int i = 0; i < L.size(); i++){
L1.push_back(L[i]);
if (i < L.size()-1){
int a = LCA(L[i], L[i+1]);
if (col[a] == 0){
col[a] = 3;
L1.push_back(a);
}
}
}
sort(L1.begin(), L1.end(), cmp);
for (int i = 0; i < L1.size(); i++)
son[L1[i]].clear();
while (!st.empty()) st.pop();
st.push(L1[0]);
for (int i = 1; i < L1.size(); i++){
while (!is_ancestor(st.top(), L1[i])) st.pop();
son[st.top()].push_back(mp(L1[i], get(st.top(), L1[i])));
st.push(L1[i]);
}
ans = +inf;
DFS2(L1[0]);
cout << ans << '\n';
for (int i = 0; i < L1.size(); i++)
col[L1[i]] = 0;
}
void solve(){
cin >> N >> Q;
for (int i = 0; i < N; i++)
adj[i].clear();
for (int i = 1; i < N; i++){
int u, v, c;
cin >> u >> v >> c;
adj[u].push_back(mp(v, c));
adj[v].push_back(mp(u, c));
}
parent[0] = -1; h[0] = 0;
for (int i = 1; i < N; i++) h[i] = -1;
t = 0;
DFS(0);
build();
while (Q--){
int k1, k2;
cin >> k1 >> k2;
L.clear();
while (k1--){
int x; cin >> x;
L.push_back(x);
col[x] = 1;
}
while (k2--){
int x; cin >> x;
L.push_back(x);
col[x] = 2;
}
solve_query();
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// cin >> T;
while (T--){
solve();
}
return 0;
}