| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1317229 | h1drogen | 공장들 (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define f first
#define s second
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define imp cout<<-1<<"\n"
#define pb push_back
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define ls v<<1
#define rs v<<1|1
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ptree tree *
const int mod=998244353;
const int INF = 1e18;
const int sqr=317;
const int N=5e5+500;
mt19937 rng(12345312);
vector<vector<pii>>g;
vector<vector<int>>gr;
vector<int>sz;
vector<int>best;
vector<int>dp;
vector<int>tin;
vector<int>tout;
vector<int>us;
int up[21][N];
int tim=0;
vector<map<int,int>>cent;
void dfs(int v,int p,int sum){
tin[v]=tim++;
dp[v]=sum;
up[0][v]=p;
for(int i=1;i<=20;i++){
up[i][v]=up[i-1][up[i-1][v]];
}
for(auto [to,c]:g[v]){
if(to!=p){
dfs(to,v,sum+c);
}
}
tout[v]=tim;
}
void precalc(int v,int p){
sz[v]=1;
for(auto [to,c]:g[v]){
if(to!=p and !us[to]){
precalc(to,v);
sz[v]+=sz[to];
}
}
}
int get(int v,int p,int n){
for(auto k:g[v]){
if(sz[k.f]>n/2 and k.f!=p and !us[k.f])
return get(k.f,v,n);
}
return v;
}
bool check(int a,int b){
return tin[a]<=tin[b] and tout[b]<=tout[a];
}
int lca(int a,int b){
if(check(a,b)) return a;
if(check(b,a)) return b;
for(int i=20;i>=0;i--){
if(!check(up[i][a],b))
a=up[i][a];
}
return up[0][a];
}
int dist(int a,int b){
return dp[a]+dp[b]-dp[lca(a,b)]*2;
}
vector<int>par;
void build(int v,int p){
precalc(v,-1);
int c=get(v,-1,sz[v]);
us[c]=1;
par[c]=p;
for(auto k:g[c]){
if(!us[k.f]){
build(k.f,c);
}
}
}
void upd(int v,int x){
best[v]=min(dist(v,x),best[v]);
if(par[v]<0)
return;
upd(par[v],x);
}
void nulify(int v,int x){
best[v]=1e18;
if(par[v]<0)
return;
nulify(par[v],x);
}
int ans=1e18;
void res(int v,int x){
ans=min(dist(v,x)+best[v],ans);
if(par[v]<0)
return;
res(par[v],x);
}
void solve(){
int n,m;
cin>>n>>m;
g.resize(n+1);
par.resize(n+1);
us.resize(n+1);
dp.resize(n+1);
cent.resize(n+1);
best.resize(n+1);
sz.resize(n+1);
tin.resize(n+1);
tout.resize(n+1);
for(int i=1;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
g[a].pb({b,c});
g[b].pb({a,c});
}
dfs(0,0,0);
build(0,-1);
for(int i=0;i<n;i++){
best[i]=1e18;
}
for(int ii=0;ii<m;ii++){
int a,b;
cin>>a>>b;
ans=1e18;
vector<int>g(a);
for(int i=0;i<a;i++){
cin>>g[i];
upd(g[i],g[i]);
}
int c;
for(int i=0;i<b;i++){
cin>>c;
res(c,c);
}
cout<<ans<<"\n";
for(int i=0;i<a;i++){
nulify(g[i],g[i]);
}
}
}
signed main(){
fast;
int t=1;
// cin>>t;
while(t--){
solve();
}
}