| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1230724 | hehebjp123 | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ii pair<ll,ll>
#define fi first
#define se second
#define all(a) a.begin(),a.end()
using namespace std;
const int N = 5e5 + 5;
const ll inf=1e18;
const int LOG = 20;
vector<ii> v[N];
vector<pair<int, int>> adj[N];
int up[N][LOG];
int depth[N];
ll dist[N];
ll tin[N],tout[N],timer=0;
void dfs(int u, int p) {
up[u][0] = p;
for (int i = 1; i < LOG; i++) {
up[u][i] = up[up[u][i - 1]][i - 1];
}
tin[u]=++timer;
for (auto [v, w] : adj[u]) {
if (v != p) {
depth[v] = depth[u] + 1;
dist[v] = dist[u] + w;
dfs(v, u);
}
}
tout[u]=timer;
}
int lca(int u, int v) {
if (depth[u] < depth[v])
swap(u, v);
for (int i = LOG - 1; i >= 0; i--)
if (up[u][i] != -1 && depth[up[u][i]] >= depth[v])
u = up[u][i];
if (u == v) return u;
for (int i = LOG - 1; i >= 0; i--) {
if (up[u][i] != -1 && up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
ll get_dist(int u, int v) {
int ancestor = lca(u, v);
return dist[u] + dist[v] - 2 * dist[ancestor];
}
bool sort_tin(ll &a,ll &b)
{
return (tin[a]<tin[b]);
}
bool is_ancestor(ll u,ll v)
{
return (tin[u]<=tin[v]&&tout[v]<=tout[u]);
}
ll ans,i,n,q,j,x,y;
ll dp[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for (int i = 1; i < n; i++) {
int x, y, w;
cin >> x >> y >> w;
adj[x].pb({y, w});
adj[y].pb({x, w});
}
for(ll i=0;i<LOG;i++)
up[0][i]=0;
depth[1] = 0;
dist[1] = 0;
dfs(0, 0);
memset(dp,-1,sizeof(dp));
vector<bool>visited(n,0);
while (q--) {
ans=inf;
ll s,t;
cin>>s>>t;
vector<ll> x(s),y(t);
for(auto &k:x) {cin>>k;}
for(auto &k:y) {cin>>k;dp[k]=0;}
vector<ll>special=x;
for(auto k:y) special.pb(k);
sort(all(special),sort_tin);
vector<ll> node=special;
for(i=1;i<special.size();i++)
node.pb(lca(special[i-1],special[i]));
sort(all(node),sort_tin);
node.erase(unique(all(node)),node.end());
stack<ll> st;
st.push(node[0]);
for(i=1;i<node.size();i++)
{
ll u=node[i];
while(!is_ancestor(st.top(),u)) st.pop();
ll x=st.top();
ll dis=get_dist(u,x);
//cout<<x<<" "<<u<<" "<<dis<<'\n';
v[u].pb({x,dis});
v[x].pb({u,dis});
st.push(u);
}
priority_queue<ii,vector<ii>,greater<ii>>pq;
for(auto k:x) pq.push({0,k});
while(1)
{
ii top=pq.top();
pq.pop();
ll dis=top.fi,u=top.se;
// cout<<dis<<" "<<u<<'\n';
if(dp[u]==0)
{
ans=dis;
break;
}
if(visited[u]) continue;
visited[u]=1;
for(auto [x,d]:v[u])
pq.push({d+dis,x});
}
cout<<ans<<'\n';
for(auto k:node) {dp[k]=-1;v[k].clear();}
for(auto k:node) visited[k]=0;
}
return 0;
}
/*
7 1
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
*/