#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
#define int long long
using ll=long long;
const ll maxN=5e5+10;
#define taskname "codeforce"
ll dp1[maxN],dp2[maxN],mn1[maxN],mn2[maxN];
const ll inf=1e15;
#define pli pair<int,int>
#define fi first
#define se second
vector<pli>g[maxN];
vector<pli>c[maxN];
ll vt[maxN];
void dfs1(ll u,ll p)
{
dp1[u]=inf;
mn1[u]=mn2[u]=inf;
for(auto vv:c[u])
{
int v=vv.fi;
int w=vv.se;
//if(v==p) {continue;}
dfs1(v,u);
dp1[u]=min(dp1[v]+w,dp1[u]);
if(dp1[v]+w<=mn1[u])
{
mn2[u]=mn1[u];
mn1[u]=dp1[v]+w;
}
else if(dp1[v]+w<=mn2[u])
{
mn2[u]=dp1[v]+w;
}
}
if(vt[u]>=2) dp1[u]=0;
}
void dfs2(ll u,ll p,ll w)
{
dp2[u]=inf;
if(vt[u]>=2) dp2[u]=0;
if(p!=0)
{
if(vt[p]>=2) dp2[u]=w;
else
{
if(dp1[u]+w==mn1[p]) dp2[u]=mn2[p]+w;
else dp2[u]=mn1[p]+w;
dp2[u]=min(dp2[u],dp2[p]+w);
}
}
for(auto vv:c[u])
{
int v=vv.fi;
int w=vv.se;
//if(v==p) continue;
dfs2(v,u,w);
}
}
#define pb push_back
ll in[maxN],out[maxN];
bool cmp(ll x,ll y)
{
return in[x]<in[y];
}
ll cnt[maxN];
ll h[maxN];
ll dd[maxN],tg=0;
ll par[maxN][21];
void dfs(ll u=1,ll p=1)
{
in[u]=++tg;
par[u][0]=p;
for(int i=1;i<=20;i++) par[u][i]=par[par[u][i-1]][i-1];
for(auto vv:g[u])
{
ll v=vv.fi;
ll w=vv.se;
if(v!=p)
{
h[v]=h[u]+1;
dd[v]=dd[u]+w;
dfs(v,u);
}
}
out[u]=tg;
}
ll LCA(ll u, ll v)
{
if(h[u]<h[v]) swap(u,v);
ll log=log2(h[u])+1;
for(int i=log;i>=0;i--)
{
if(h[par[u][i]]>=h[v]) u=par[u][i];
}
if(u==v) return u;
for(int i=log;i>=0;i--)
{
if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
}
return par[u][0];
}
ll dis(ll u,ll v)
{
return dd[u]+dd[v]-2*dd[LCA(u,v)];
}
bool isParent(ll x,ll y)
{
return in[x]<=in[y]&&out[y]<=out[x];
}
ll Query(ll s,ll x[],ll t,ll y[])
{
vector<ll> vv;
for(int i=0;i<s;i++) vv.pb(x[i]),vt[x[i]]+=1;
for(int i=0;i<t;i++) vv.pb(y[i]),vt[y[i]]+=2;
sort(vv.begin(),vv.end(),cmp);
ll k=vv.size();
for(int i=1;i<k;i++)
{
ll v=LCA(vv[i],vv[i-1]);
vv.pb(v);
}
sort(vv.begin(),vv.end(),cmp);
stack<int>st;
for(int i=0;i<vv.size();i++)
{
if(cnt[vv[i]]==0)
{
while(!st.empty()&&(!isParent(st.top(),vv[i]))) st.pop();
if(!st.empty()) c[st.top()].pb({vv[i],dis(st.top(),vv[i])});
st.push(vv[i]);
cnt[vv[i]]=1;
}
}
//cout << '\n';
dfs1(vv[0],0);
dfs2(vv[0],0,0);
ll ans=inf;
for(int i=0;i<vv.size();i++)
{
if(vt[vv[i]]==1||vt[vv[i]]==3)
{
ans=min(ans,min(dp1[vv[i]],dp2[vv[i]]));
}
}
for(int i=0;i<vv.size();i++)
{
cnt[vv[i]]=0;
c[vv[i]].clear();
vt[vv[i]]=0;
}
return ans;
}
void Init(int N,int A[],int B[],int D[])
{
for(int i=0;i<N-1;i++)
{
g[A[i]].pb({B[i],D[i]});
g[B[i]].pb({A[i],D[i]});
}
dfs();
}
Compilation message
factories.cpp: In function 'll Query(ll, ll*, ll, ll*)':
factories.cpp:127:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int i=0;i<vv.size();i++)
| ~^~~~~~~~~~
factories.cpp:141:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for(int i=0;i<vv.size();i++)
| ~^~~~~~~~~~
factories.cpp:148:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for(int i=0;i<vv.size();i++)
| ~^~~~~~~~~~
/usr/bin/ld: /tmp/ccBlUq5T.o: in function `main':
grader.cpp:(.text.startup+0x37d): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status
