#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const int maxN = 5e5 + 5, LOG = 20;
const long long INF = (long long) 1e18 + 5;
vector<pair<int, long long>> adj[maxN];
int h[maxN], par[LOG][maxN], tin[maxN], tout[maxN], timedfs = 0;
long long w[maxN];
void dfs(int i, int pre){
tin[i] = ++timedfs;
for(pair<int, long long> e : adj[i]){
int x = e.first, c = e.second;
if(x == pre) continue;
h[x] = h[i] + 1, w[x] = w[i] + c;
par[0][x] = i;
for(int j = 1; j < LOG; j++) par[j][x] = par[j - 1][par[j - 1][x]];
dfs(x, i);
}
tout[i] = timedfs;
}
int lca(int x, int y){
if(h[x] < h[y]) swap(x, y);
int d = h[x] - h[y];
for(int i = 0; i < LOG; i++){
if(d & (1 << i)) x = par[i][x];
}
if(x == y) return x;
for(int i = LOG - 1; i >= 0; i--){
if(par[i][x] != par[i][y]) x = par[i][x], y = par[i][y];
}
return par[0][x];
}
map<pair<int, long long>, long long> mp;
int label[maxN];
void Init(int N, int A[], int B[], int D[]){
for(int i = 0; i < N - 1; i++){
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0);
memset(label, -1, sizeof label);
}
vector<pair<int, long long>> adj2[maxN];
bool in(int x, int y){
return tin[x] <= tin[y] && tin[y] <= tout[x];
}
long long dp[2][maxN], ans;
void dfs2(int i){
for(pair<int, long long> e : adj2[i]){
int x = e.first, w = e.second;
dfs2(x);
dp[0][i] = min(dp[0][i], dp[0][x] + w);
dp[1][i] = min(dp[1][i], dp[1][x] + w);
}
if(label[i] != -1){
ans = min(ans, dp[label[i] ^ 1][i]);
dp[label[i]][i] = 0;
}
ans = min(ans, dp[0][i] + dp[1][i]);
}
long long Query(int S, int X[], int T, int Y[]){
vector<int> v; ans = INF;
for(int i = 0; i < S; i++){
if(label[X[i]] == 1) return 0;
v.push_back(X[i]), label[X[i]] = 0;
}
for(int i = 0; i < T; i++){
if(label[Y[i]] == 0) return 0;
v.push_back(Y[i]), label[Y[i]] = 1;
}
sort(v.begin(), v.end(), [](int x, int y){return tin[x] < tin[y];});
for(int i = v.size() - 2; i >= 0; i--){
v.push_back(lca(v[i], v[i + 1]));
}
sort(v.begin(), v.end(), [](int x, int y){return tin[x] < tin[y];});
v.resize(unique(v.begin(), v.end()) - v.begin());
stack<int> st; st.push(v[0]);
for(int i = 1; i < (int) v.size(); i++){
while(st.size() && !in(st.top(), v[i])) st.pop();
adj2[st.top()].push_back({v[i], w[v[i]] - w[st.top()]});
st.push(v[i]);
}
for(int x : v) dp[0][x] = dp[1][x] = INF;
dfs2(v[0]);
for(int x : v) label[x] = -1;
for(int x : v) adj2[x].clear();
while(st.size()) st.pop();
return ans;
}
#ifdef LOCAL
const int MAX = 1e3 + 5;
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
int x[MAX], y[MAX], d[MAX];
for(int i = 0; i < n - 1; i++){
cin >> x[i] >> y[i] >> d[i];
}
Init(n, x, y, d);
for(int i = 1; i <= q; i++){
int s, t; cin >> s >> t;
int a[MAX], b[MAX];
for(int i = 0; i < s; i++) cin >> a[i];
for(int i = 0; i < t; i++) cin >> b[i];
cout << Query(s, a, t, b) << '\n';
}
return 0;
}
#endif
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
26664 KB |
Output is correct |
2 |
Correct |
716 ms |
44304 KB |
Output is correct |
3 |
Correct |
700 ms |
44296 KB |
Output is correct |
4 |
Incorrect |
647 ms |
44228 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
26204 KB |
Output is correct |
2 |
Correct |
1279 ms |
139044 KB |
Output is correct |
3 |
Incorrect |
1772 ms |
143652 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
26664 KB |
Output is correct |
2 |
Correct |
716 ms |
44304 KB |
Output is correct |
3 |
Correct |
700 ms |
44296 KB |
Output is correct |
4 |
Incorrect |
647 ms |
44228 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |