| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1108926 | doducanh | Factories (JOI14_factories) | C++14 | 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.
///breaker
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int maxn=5e5+7;
const int inf=5e5+7;
vector<ii>adj[maxn];
int sz[maxn];
bool used[maxn];
int p[25][maxn];
ll up[25][maxn];
ll minn[maxn];
int h[maxn];
vector<int>ancestors[maxn];
int n,q;
int dfs(int u,int par)
{
sz[u]=1;
for(auto [v,w]:adj[u]){
if(v==par||used[v])continue;
sz[u]+=dfs(v,u);
}
return sz[u];
}
void dfs1(int u,int par)
{
for(auto [v,w]:adj[u]){
if(v==par)continue;
p[0][v]=u;
up[0][v]=w;
h[v]=h[u]+1;
dfs1(v,u);
}
}
void dfs2(int u,int par,int cen)
{
ancestors[u].push_back(cen);
for(auto [v,w]:adj[u]){
if(v==par||used[v])continue;
dfs2(v,u,cen);
}
}
int getcen(int u,int par,int treesize)
{
for(auto [v,w]:adj[u]){
if(v==par||used[v])continue;
if((sz[v]<<1)>treesize)return getcen(v,u,treesize);
}
return u;
}
void buildcen(int u,int par)
{
int C=getcen(u,0,dfs(u,0));
used[C]=1;
dfs2(C,0,C);
for(auto [v,w]:adj[u]){
if(v==par||used[v])continue;
buildcen(v,u);
}
}
ll path(int u,int v)
{
if(h[u]<h[v])swap(u,v);
int del=h[u]-h[v];
ll ans=0;
for(int i=20;i>=0;i--)if(bit(del,i)){
ans+=up[i][u];
u=p[i][u];
}
if(u==v)return ans;
for(int i=20;i>=0;i--)if(p[i][u]!=p[i][v]){
ans+=up[i][u];
ans+=up[i][v];
u=p[i][u];
v=p[i][v];
}
ans+=up[0][u];
ans+=up[0][v];
return ans;
}
void sol(void){
cin>>n>>q;
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
dfs1(0,0);
for(int i=1;i<=20;i++){
for(int j=0;j<n;j++){
p[i][j]=p[i-1][p[i-1][j]];
up[i][j]=up[i-1][j]+up[i-1][p[i-1][j]];
}
}
buildcen(0,0);
for(int i=0;i<n;i++){
minn[i]=inf;
}
while(q--){
int s,t;
cin>>s>>t;
vector<int>tmp;
for(int i=1;i<=s;i++){
int x;
cin>>x;
tmp.push_back(x);
for(int y:ancestors[x]){
minn[y]=min(minn[y],path(x,y));
}
}
ll ans=inf;
for(int i=1;i<=t;i++){
int x;
cin>>x;
for(int y:ancestors[x]){
ans=min(ans,minn[y]+path(x,y));
}
}
cout<<ans<<"\n";
for(int x:tmp){
for(int y:ancestors[x]){
minn[y]=inf;
}
}
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
while(t--){
sol();
}
// you should actually read the stuff at the bottom
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/