#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
#define int long long
#define inf 1000000000
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
using namespace std;
int n,q;
vii ke[maxn];
int par[maxn][20],sz[maxn],h[maxn],d[maxn];
int ind[maxn],head[maxn],cnt = 1;
vector<array<int,4>> adj;
int minn[maxn][2];
void dfs(int u,int parent)
{
sz[u] = 1;
for(auto [v,w] : ke[u])
{
if(v == parent) continue;
par[v][0] = u;
h[v] = h[u] + 1;
d[v] = d[u] + w;
dfs(v,u);
sz[u] += sz[v];
}
}
void hld(int u,int parent)
{
if(head[cnt] == 0) head[cnt] = u;
ind[u] = cnt;
int sc = -1,maxx = -1;
for(auto [v,w] : ke[u]) if(v != parent)
{
if(maxx < sz[v])
{
maxx = sz[v];
sc = v;
}
}
if(sc != -1) hld(sc,u);
for(auto [v,w] : ke[u]) if(v != parent and v != sc)
{
cnt++;
hld(v,u);
}
}
void get(int u,int t)
{
int val = d[u];
int uchain,vchain = ind[1];
while(1)
{
uchain = ind[u];
adj.push_back({uchain,u,val,t});
if(uchain == vchain) return;
u = ind[u];
u = par[head[u]][0];
}
}
main()
{
#define name "TASK"
if(fopen(name".inp","r"))
{
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
fo(i,1,n - 1)
{
int u,v,w;
cin >> u >> v >> w;
u++;
v++;
ke[u].pb(v,w);
ke[v].pb(u,w);
}
dfs(1,1);
fo(j,1,19) fo(i,1,n) par[i][j] = par[par[i][j - 1]][j - 1];
hld(1,1);
while(q--)
{
int ans = 2e18;
int n1,n2;
cin >> n1 >> n2;
fo(i,1,n1)
{
int x;
cin >> x;
get(x + 1,0);
}
fo(i,1,n2)
{
int x;
cin >> x;
get(x + 1,1);
}
sort(adj.begin(),adj.end(),[](array<int,4> a,array<int,4> b)
{
return d[a[1]] > d[b[1]];
});
fo(i,1,cnt) fo(j,0,1) minn[i][j] = 2e18;
for(auto [p,v,dist,t] : adj)
{
ans = min(ans,minn[p][1 - t] - 2 * d[v] + dist);
minn[p][t] = min(minn[p][t],dist);
}
adj.clear();
cout << ans;
en;
}
}
Compilation message
factories.cpp:90:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
90 | main()
| ^~~~
factories.cpp: In function 'int main()':
factories.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | freopen(name".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
factories.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | freopen(name".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc8Xf2bB.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccfnwU2y.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc8Xf2bB.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
