#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e9;
vector<pair<int, int>> adj[maxN];
int n, q;
vector<int> tour;
int pos[maxN];
int rmq[maxN][21];
int lg[maxN];
int depth[maxN];
vector<int> vc[maxN];
int f[maxN];
int F[maxN];
int dp[maxN];
int vis[maxN];
int parCent[maxN];
void Log()
{
for(int i=2; i<maxN; i++)
lg[i] = lg[i / 2] + 1;
}
void predfs(int u, int par)
{
pos[u] = tour.size();
tour.pb(u);
for(auto a : adj[u])
{
int v = a.fi, w = a.se;
if(v == par) continue;
depth[v] = depth[u] + 1;
f[v] = f[u] + w;
predfs(v, u);
tour.pb(u);
}
}
int mini(int u, int v)
{
return depth[u] < depth[v] ? u : v;
}
int LCA(int u, int v)
{
int l = min(pos[u], pos[v]), r = max(pos[u], pos[v]);
int k = lg[r - l + 1];
return mini(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}
int dist(int u, int v)
{
return f[u] + f[v] - 2 * f[LCA(u, v)];
}
int dfs(int u, int par)
{
dp[u] = 1;
for(auto a : adj[u])
{
int v = a.fi;
if(v == par || vis[v])
continue;
dp[u] += dfs(v, u);
}
return dp[u];
}
int Find_Centroid(int u, int par, int sz)
{
for(auto a : adj[u])
{
int v = a.fi;
if(v == par || vis[v])
continue;
if(dp[v] > sz / 2)
return Find_Centroid(v, u, sz);
}
return u;
}
int Decompose(int u)
{
int root = Find_Centroid(u, 0, dfs(u, 0));
vis[root] = 1;
for(auto a : adj[root])
{
int v = a.fi;
if(vis[v])
continue;
parCent[Decompose(v)] = root;
}
return root;
}
void update(int u)
{
for(int v=u; v; v=parCent[v])
{
F[v] = min(F[v], f[u] - 2 * f[v]);
}
}
void del(int u)
{
for(int v=u; v; v=parCent[v])
{
F[v] = oo;
}
}
int get(int u)
{
int res = oo;
for(int v=u; v; v=parCent[v]) res = min(res, F[v] + f[u]);
return res;
}
void Init(int N, int A[], int B[], int D[])
{
n = N;
for(int i=0; i<n; i++)
{
int u = A[i] + 1, v = B[i] + 1, w = D[i];
adj[u].pb({v, w});
adj[v].pb({u, w});
}
Log();
depth[1] = 1;
tour.clear();
//cout << Decompose(1);return;
predfs(Decompose(1), 0);
for (int i = 0; i < tour.size(); i++)
{
rmq[i][0] = tour[i];
}
for (int i = 1; i <=20; i++)
{
for (int j = 0; j < tour.size(); j++)
{
if (j + (1 << (i - 1)) >= tour.size())
rmq[j][i] = rmq[j][i - 1];
else
rmq[j][i] = mini(rmq[j][i - 1], rmq[j + (1 << (i - 1))][i - 1]);
}
}
// cout << LCA(4, 7);return;
fill(F, F + n + 1, oo);
//cout << dist(4, 7);return;
}
long long Query(int S, int X[], int T, int Y[])
{
for(int i=0; i<S; i++)
{
int u = X[i] + 1;
update(u);
}
int res = oo;
for(int i=0; i<T; i++)
{
int u = Y[i] + 1;
res = min(res, get(u));
}
return res;
}
void ReadInput()
{
cin >> n >> q;
for(int i=1; i<n; i++)
{
int u, v, w;
cin >> u >> v >> w;
u++;
v++;
adj[u].pb({v, w});
adj[v].pb({u, w});
}
}
void Solve()
{
Log();
depth[1] = 1;
tour.clear();
//cout << Decompose(1);return;
predfs(Decompose(1), 0);
for (int i = 0; i < tour.size(); i++)
{
rmq[i][0] = tour[i];
}
for (int i = 1; i <=20; i++)
{
for (int j = 0; j < tour.size(); j++)
{
if (j + (1 << (i - 1)) >= tour.size())
rmq[j][i] = rmq[j][i - 1];
else
rmq[j][i] = mini(rmq[j][i - 1], rmq[j + (1 << (i - 1))][i - 1]);
}
}
// cout << LCA(4, 7);return;
fill(F, F + n + 1, oo);
//cout << dist(4, 7);return;
while(q--)
{
int x, y;
cin >> x >> y;
vector<int> vc;
for(int i=1; i<=x; i++)
{
int u;
cin >> u;
u++;
update(u);
vc.pb(u);
}
int res = oo;
for(int i=1; i<=y; i++)
{
int v;
cin >> v;
v++;
res = min(res, get(v));
}
for(int u : vc) del(u);
cout << res << '\n';
}
}
/*int32_t main()
{
freopen("x.inp", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ReadInput();
Solve();
}*/
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e9;
vector<pair<int, int>> adj[maxN];
int n, q;
vector<int> tour;
int pos[maxN];
int rmq[maxN][21];
int lg[maxN];
int depth[maxN];
vector<int> vc[maxN];
int f[maxN];
int F[maxN];
int dp[maxN];
int vis[maxN];
int parCent[maxN];
void Log()
{
for(int i=2; i<maxN; i++)
lg[i] = lg[i / 2] + 1;
}
void predfs(int u, int par)
{
pos[u] = tour.size();
tour.pb(u);
for(auto a : adj[u])
{
int v = a.fi, w = a.se;
if(v == par) continue;
depth[v] = depth[u] + 1;
f[v] = f[u] + w;
predfs(v, u);
tour.pb(u);
}
}
int mini(int u, int v)
{
return depth[u] < depth[v] ? u : v;
}
int LCA(int u, int v)
{
int l = min(pos[u], pos[v]), r = max(pos[u], pos[v]);
int k = lg[r - l + 1];
return mini(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}
int dist(int u, int v)
{
return f[u] + f[v] - 2 * f[LCA(u, v)];
}
int dfs(int u, int par)
{
dp[u] = 1;
for(auto a : adj[u])
{
int v = a.fi;
if(v == par || vis[v])
continue;
dp[u] += dfs(v, u);
}
return dp[u];
}
int Find_Centroid(int u, int par, int sz)
{
for(auto a : adj[u])
{
int v = a.fi;
if(v == par || vis[v])
continue;
if(dp[v] > sz / 2)
return Find_Centroid(v, u, sz);
}
return u;
}
int Decompose(int u)
{
int root = Find_Centroid(u, 0, dfs(u, 0));
vis[root] = 1;
for(auto a : adj[root])
{
int v = a.fi;
if(vis[v])
continue;
parCent[Decompose(v)] = root;
}
return root;
}
void update(int u)
{
for(int v=u; v; v=parCent[v])
{
F[v] = min(F[v], f[u] - 2 * f[v]);
}
}
void del(int u)
{
for(int v=u; v; v=parCent[v])
{
F[v] = oo;
}
}
int get(int u)
{
int res = oo;
for(int v=u; v; v=parCent[v]) res = min(res, F[v] + f[u]);
return res;
}
void Init(int N, int A[], int B[], int D[])
{
n = N;
for(int i=0; i<n; i++)
{
int u = A[i] + 1, v = B[i] + 1, w = D[i];
adj[u].pb({v, w});
adj[v].pb({u, w});
}
Log();
depth[1] = 1;
tour.clear();
//cout << Decompose(1);return;
predfs(Decompose(1), 0);
for (int i = 0; i < tour.size(); i++)
{
rmq[i][0] = tour[i];
}
for (int i = 1; i <=20; i++)
{
for (int j = 0; j < tour.size(); j++)
{
if (j + (1 << (i - 1)) >= tour.size())
rmq[j][i] = rmq[j][i - 1];
else
rmq[j][i] = mini(rmq[j][i - 1], rmq[j + (1 << (i - 1))][i - 1]);
}
}
// cout << LCA(4, 7);return;
fill(F, F + n + 1, oo);
//cout << dist(4, 7);return;
}
long long Query(int S, int X[], int T, int Y[])
{
for(int i=0; i<S; i++)
{
int u = X[i] + 1;
update(u);
}
int res = oo;
for(int i=0; i<T; i++)
{
int u = Y[i] + 1;
res = min(res, get(u));
}
return res;
}
void ReadInput()
{
cin >> n >> q;
for(int i=1; i<n; i++)
{
int u, v, w;
cin >> u >> v >> w;
u++;
v++;
adj[u].pb({v, w});
adj[v].pb({u, w});
}
}
void Solve()
{
Log();
depth[1] = 1;
tour.clear();
//cout << Decompose(1);return;
predfs(Decompose(1), 0);
for (int i = 0; i < tour.size(); i++)
{
rmq[i][0] = tour[i];
}
for (int i = 1; i <=20; i++)
{
for (int j = 0; j < tour.size(); j++)
{
if (j + (1 << (i - 1)) >= tour.size())
rmq[j][i] = rmq[j][i - 1];
else
rmq[j][i] = mini(rmq[j][i - 1], rmq[j + (1 << (i - 1))][i - 1]);
}
}
// cout << LCA(4, 7);return;
fill(F, F + n + 1, oo);
//cout << dist(4, 7);return;
while(q--)
{
int x, y;
cin >> x >> y;
vector<int> vc;
for(int i=1; i<=x; i++)
{
int u;
cin >> u;
u++;
update(u);
vc.pb(u);
}
int res = oo;
for(int i=1; i<=y; i++)
{
int v;
cin >> v;
v++;
res = min(res, get(v));
}
for(int u : vc) del(u);
cout << res << '\n';
}
}
/*int32_t main()
{
freopen("x.inp", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ReadInput();
Solve();
}*/
Compilation message
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int i = 0; i < tour.size(); i++)
| ~~^~~~~~~~~~~~~
factories.cpp:138:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for (int j = 0; j < tour.size(); j++)
| ~~^~~~~~~~~~~~~
factories.cpp:140:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | if (j + (1 << (i - 1)) >= tour.size())
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
factories.cpp: In function 'void Solve()':
factories.cpp:185:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
185 | for (int i = 0; i < tour.size(); i++)
| ~~^~~~~~~~~~~~~
factories.cpp:192:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
192 | for (int j = 0; j < tour.size(); j++)
| ~~^~~~~~~~~~~~~
factories.cpp:194:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
194 | if (j + (1 << (i - 1)) >= tour.size())
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
factories.cpp: At global scope:
factories.cpp:246:9: error: redefinition of 'std::mt19937 rng'
246 | mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
| ^~~
factories.cpp:10:9: note: 'std::mt19937 rng' previously declared here
10 | mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
| ^~~
factories.cpp:247:11: error: redefinition of 'const int maxN'
247 | const int maxN = 1e6 + 5;
| ^~~~
factories.cpp:11:11: note: 'const int maxN' previously defined here
11 | const int maxN = 1e6 + 5;
| ^~~~
factories.cpp:248:11: error: redefinition of 'const int mod'
248 | const int mod = 1e9 + 7;
| ^~~
factories.cpp:12:11: note: 'const int mod' previously defined here
12 | const int mod = 1e9 + 7;
| ^~~
factories.cpp:249:10: error: redefinition of 'const ll oo'
249 | const ll oo = 1e9;
| ^~
factories.cpp:13:10: note: 'const ll oo' previously defined here
13 | const ll oo = 1e9;
| ^~
factories.cpp:250:24: error: redefinition of 'std::vector<std::pair<int, int> > adj [1000005]'
250 | vector<pair<int, int>> adj[maxN];
| ^~~
factories.cpp:14:24: note: 'std::vector<std::pair<int, int> > adj [1000005]' previously declared here
14 | vector<pair<int, int>> adj[maxN];
| ^~~
factories.cpp:251:5: error: redefinition of 'int n'
251 | int n, q;
| ^
factories.cpp:15:5: note: 'int n' previously declared here
15 | int n, q;
| ^
factories.cpp:251:8: error: redefinition of 'int q'
251 | int n, q;
| ^
factories.cpp:15:8: note: 'int q' previously declared here
15 | int n, q;
| ^
factories.cpp:252:13: error: redefinition of 'std::vector<int> tour'
252 | vector<int> tour;
| ^~~~
factories.cpp:16:13: note: 'std::vector<int> tour' previously declared here
16 | vector<int> tour;
| ^~~~
factories.cpp:253:5: error: redefinition of 'int pos [1000005]'
253 | int pos[maxN];
| ^~~
factories.cpp:17:5: note: 'int pos [1000005]' previously declared here
17 | int pos[maxN];
| ^~~
factories.cpp:254:5: error: redefinition of 'int rmq [1000005][21]'
254 | int rmq[maxN][21];
| ^~~
factories.cpp:18:5: note: 'int rmq [1000005][21]' previously declared here
18 | int rmq[maxN][21];
| ^~~
factories.cpp:255:5: error: redefinition of 'int lg [1000005]'
255 | int lg[maxN];
| ^~
factories.cpp:19:5: note: 'int lg [1000005]' previously declared here
19 | int lg[maxN];
| ^~
factories.cpp:256:5: error: redefinition of 'int depth [1000005]'
256 | int depth[maxN];
| ^~~~~
factories.cpp:20:5: note: 'int depth [1000005]' previously declared here
20 | int depth[maxN];
| ^~~~~
factories.cpp:257:13: error: redefinition of 'std::vector<int> vc [1000005]'
257 | vector<int> vc[maxN];
| ^~
factories.cpp:21:13: note: 'std::vector<int> vc [1000005]' previously declared here
21 | vector<int> vc[maxN];
| ^~
factories.cpp:258:5: error: redefinition of 'int f [1000005]'
258 | int f[maxN];
| ^
factories.cpp:22:5: note: 'int f [1000005]' previously declared here
22 | int f[maxN];
| ^
factories.cpp:259:5: error: redefinition of 'int F [1000005]'
259 | int F[maxN];
| ^
factories.cpp:23:5: note: 'int F [1000005]' previously declared here
23 | int F[maxN];
| ^
factories.cpp:260:5: error: redefinition of 'int dp [1000005]'
260 | int dp[maxN];
| ^~
factories.cpp:24:5: note: 'int dp [1000005]' previously declared here
24 | int dp[maxN];
| ^~
factories.cpp:261:5: error: redefinition of 'int vis [1000005]'
261 | int vis[maxN];
| ^~~
factories.cpp:25:5: note: 'int vis [1000005]' previously declared here
25 | int vis[maxN];
| ^~~
factories.cpp:262:5: error: redefinition of 'int parCent [1000005]'
262 | int parCent[maxN];
| ^~~~~~~
factories.cpp:26:5: note: 'int parCent [1000005]' previously declared here
26 | int parCent[maxN];
| ^~~~~~~
factories.cpp:263:6: error: redefinition of 'void Log()'
263 | void Log()
| ^~~
factories.cpp:27:6: note: 'void Log()' previously defined here
27 | void Log()
| ^~~
factories.cpp:268:6: error: redefinition of 'void predfs(int, int)'
268 | void predfs(int u, int par)
| ^~~~~~
factories.cpp:32:6: note: 'void predfs(int, int)' previously defined here
32 | void predfs(int u, int par)
| ^~~~~~
factories.cpp:282:5: error: redefinition of 'int mini(int, int)'
282 | int mini(int u, int v)
| ^~~~
factories.cpp:46:5: note: 'int mini(int, int)' previously defined here
46 | int mini(int u, int v)
| ^~~~
factories.cpp:286:5: error: redefinition of 'int LCA(int, int)'
286 | int LCA(int u, int v)
| ^~~
factories.cpp:50:5: note: 'int LCA(int, int)' previously defined here
50 | int LCA(int u, int v)
| ^~~
factories.cpp:292:5: error: redefinition of 'int dist(int, int)'
292 | int dist(int u, int v)
| ^~~~
factories.cpp:56:5: note: 'int dist(int, int)' previously defined here
56 | int dist(int u, int v)
| ^~~~
factories.cpp:296:5: error: redefinition of 'int dfs(int, int)'
296 | int dfs(int u, int par)
| ^~~
factories.cpp:60:5: note: 'int dfs(int, int)' previously defined here
60 | int dfs(int u, int par)
| ^~~
factories.cpp:308:5: error: redefinition of 'int Find_Centroid(int, int, int)'
308 | int Find_Centroid(int u, int par, int sz)
| ^~~~~~~~~~~~~
factories.cpp:72:5: note: 'int Find_Centroid(int, int, int)' previously defined here
72 | int Find_Centroid(int u, int par, int sz)
| ^~~~~~~~~~~~~
factories.cpp:320:5: error: redefinition of 'int Decompose(int)'
320 | int Decompose(int u)
| ^~~~~~~~~
factories.cpp:84:5: note: 'int Decompose(int)' previously defined here
84 | int Decompose(int u)
| ^~~~~~~~~
factories.cpp:333:6: error: redefinition of 'void update(int)'
333 | void update(int u)
| ^~~~~~
factories.cpp:97:6: note: 'void update(int)' previously defined here
97 | void update(int u)
| ^~~~~~
factories.cpp:340:6: error: redefinition of 'void del(int)'
340 | void del(int u)
| ^~~
factories.cpp:104:6: note: 'void del(int)' previously defined here
104 | void del(int u)
| ^~~
factories.cpp:347:5: error: redefinition of 'int get(int)'
347 | int get(int u)
| ^~~
factories.cpp:111:5: note: 'int get(int)' previously defined here
111 | int get(int u)
| ^~~
factories.cpp:353:6: error: redefinition of 'void Init(int, int*, int*, int*)'
353 | void Init(int N, int A[], int B[], int D[])
| ^~~~
factories.cpp:117:6: note: 'void Init(int, int*, int*, int*)' previously defined here
117 | void Init(int N, int A[], int B[], int D[])
| ^~~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:367:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
367 | for (int i = 0; i < tour.size(); i++)
| ~~^~~~~~~~~~~~~
factories.cpp:374:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
374 | for (int j = 0; j < tour.size(); j++)
| ~~^~~~~~~~~~~~~
factories.cpp:376:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
376 | if (j + (1 << (i - 1)) >= tour.size())
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
factories.cpp: At global scope:
factories.cpp:386:11: error: redefinition of 'long long int Query(int, int*, int, int*)'
386 | long long Query(int S, int X[], int T, int Y[])
| ^~~~~
factories.cpp:150:11: note: 'long long int Query(int, int*, int, int*)' previously defined here
150 | long long Query(int S, int X[], int T, int Y[])
| ^~~~~
factories.cpp:401:6: error: redefinition of 'void ReadInput()'
401 | void ReadInput()
| ^~~~~~~~~
factories.cpp:165:6: note: 'void ReadInput()' previously defined here
165 | void ReadInput()
| ^~~~~~~~~
factories.cpp:414:6: error: redefinition of 'void Solve()'
414 | void Solve()
| ^~~~~
factories.cpp:178:6: note: 'void Solve()' previously defined here
178 | void Solve()
| ^~~~~
factories.cpp: In function 'void Solve()':
factories.cpp:421:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
421 | for (int i = 0; i < tour.size(); i++)
| ~~^~~~~~~~~~~~~
factories.cpp:428:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
428 | for (int j = 0; j < tour.size(); j++)
| ~~^~~~~~~~~~~~~
factories.cpp:430:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
430 | if (j + (1 << (i - 1)) >= tour.size())
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
