| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 372616 | erfanmir | 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.
// In the name of god
//#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define lc(x) (x) << 1
#define rc(x) (x) << 1 | 1
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define mp make_pair
const int MAXN = 1e6 + 10;
const int MAXLG = 20;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 1e18;
int n, par[MAXN][MAXLG], h[MAXN], st[MAXN], ft[MAXN], cnt, r[MAXN], b[MAXN];
stack<int> stk;
vector<int> vlc[MAXN];
vector<pii> adj[MAXN];
ll dp[MAXN], rd[MAXN], bd[MAXN];
int A1[MAXN], B1[MAXN], D1[MAXN], X1[MAXN], Y1[MAXN], S1, T1, q;
void dfs(int v = 1){
st[v] = ++cnt;
for(auto u : adj[v]){
if(u.F == par[v][0]){
continue;
}
h[u.F] = h[v] + 1;
dp[u.F] = dp[v] + u.S;
par[u.F][0] = v;
dfs(u.F);
}
ft[v] = cnt;
}
int edq(int u, int val){
for(int i = 0; i < MAXLG; i++){
if(val & 1){
u = par[u][i];
}
val /= 2;
}
return u;
}
int lca(int v, int u){
if(h[v] > h[u]){
swap(v, u);
}
u = edq(u, h[u] - h[v]);
if(v == u){
return v;
}
for(int i = MAXLG - 1; ~i; i--){
if(par[v][i] == par[u][i]){
continue;
}
v = par[v][i];
u = par[u][i];
}
return par[v][0];
}
bool cmp(int A, int B){
return st[A] < st[B];
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for(int i = 0; i < n - 1; i++){
adj[A[i] + 1].push_back(mp(B[i] + 1, D[i]));
adj[B[i] + 1].push_back(mp(A[i] + 1, D[i]));
}
dfs();
for(int i = 1; i <= n; i++){
for(int j = 1; j < MAXLG; j++){
par[i][j] = par[par[i][j - 1]][j - 1];
}
}
}
void sfd(int v){
rd[v] = bd[v] = INF;
if(b[v]){
bd[v] = 0;
}
if(r[v]){
rd[v] = 0;
}
for(auto u : vlc[v]){
sfd(u);
bd[v] = min(bd[v], bd[u] - dp[v] + dp[u]);
rd[v] = min(rd[v], rd[u] - dp[v] + dp[u]);
}
}
ll Query(int S, int X[], int T, int Y[]){
ll ans = INF;
vector<int> vec;
for(int i = 0; i < S; i++){
vec.push_back(X[i] + 1);
b[X[i] + 1] = 1;
}
for(int i = 0; i < T; i++){
vec.push_back(Y[i] + 1);
r[Y[i] + 1] = 1;
}
sort(all(vec), cmp);
for(int i = 1; i < S + T; i++){
vec.push_back(lca(vec[i], vec[i - 1]));
}
sort(all(vec));
vec.resize(unique(all(vec)) - vec.begin());
stk.push(vec[0]);
for(int i = 1; i < (int)vec.size(); i++){
while((int)stk.size() && (st[stk.top()] > st[vec[i]] || ft[vec[i]] > ft[stk.top()])){
stk.pop();
}
if((int)stk.size()){
vlc[stk.top()].push_back(vec[i]);
}
stk.push(vec[i]);
}
sfd(vec[0]);
for(auto v : vec){
vlc[v].clear();
ans = min(ans, bd[v] + rd[v]);
b[v] = r[v] = 0;
}
return ans;
}
int main(){
scanf("%d %d", &n, &q);
for(int i = 0; i < n - 1; i++){
scanf("%d %d %d", A1 + i, B1 + i, D1 + i);
}
Init(n, A1, B1, D1);
while(q--){
scanf("%d %d", &S1, &T1);
for(int i = 0; i < S1; i++){
scanf("%d", X1 + i);
}
for(int i = 0; i < T1; i++){
scanf("%d", Y1 + i);
}
printf("%lld\n", Query(S1, X1, T1, Y1));
}
}