#include <bits/stdc++.h>
#include "factories.h"
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 1e9+7;
const ll inf = 2e18;
const ll blocksz = 320;
const ll N = 5e5+8;
vpll g[N],vg[N];
ll n,q,tin[N],tout[N],tdfs,h[N],up[N][20],d[N];
void dfs_pre(ll u, ll p){
tin[u] = ++tdfs;
for(pll ed:g[u]){
ll v = ed.fi, w = ed.se;
if(v == p) continue;
h[v] = h[u]+1;
d[v] = d[u]+w;
up[v][0] = u;
for(ll i = 1; i < 20; i++) up[v][i] = up[up[v][i-1]][i-1];
dfs_pre(v,u);
}
tout[u] = tdfs;
}
ll lca(ll u, ll v){
if(h[u] < h[v]) swap(u,v);
ll k = h[u]-h[v];
for(ll i = 0; i < 20; i++){
if(k>>i&1) u = up[u][i];
}
if(u == v) return u;
for(ll i = 0; i < 20; i++){
if(up[u][i] != up[v][i]){
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
ll dist(ll u, ll v){
return d[u]+d[v]-2*d[lca(u,v)];
}
bool is_anc(ll u, ll v){
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
ll dp[N][2];
bool mark1[N],mark2[N];
void dfs(ll u, ll p){
for(pll ed:vg[u]){
ll v = ed.fi, w = ed.se;
if(v == p) continue;
dfs(v,u);
dp[u][0] = min(dp[u][0],dp[v][0]+w);
dp[u][1] = min(dp[u][1],dp[v][1]+w);
}
if(mark1[u]) dp[u][0] = 0;
if(mark2[u]) dp[u][1] = 0;
}
void Init(int N, int A[], int B[], int D[]){
for(ll i = 0; i < n-1; i++){
ll u,v,w;cin >> u >> v >> w;
g[A[i]].pb({B[i],D[i]});
g[B[i]].pb({A[i],D[i]});
}
dfs_pre(0,0);
}
long long Query(int S, int X[], int T, int Y[]){
vi vertex;
for(ll i = 0; i < S; i++){
vertex.pb(X[i]);
mark1[X[i]] = 1;
}
for(ll i = 0; i < T; i++){
vertex.pb(Y[i]);
mark2[Y[i]] = 1;
}
sort(all(vertex),[&](ll u, ll v){
return tin[u] < tin[v];
});
ll m = vertex.size();
for(ll i = 1; i < m; i++){
if(vertex[i-1] == vertex[i]){
if(mark1[vertex[i-1]] && mark2[vertex[i]]) return 0;
if(mark2[vertex[i-1]] && mark1[vertex[i]]) return 0;
}
ll l = lca(vertex[i-1],vertex[i]);
vertex.pb(l);
}
sort(all(vertex),[&](ll u, ll v){
return tin[u] < tin[v];
});
vertex.erase(unique(all(vertex)),vertex.end());
stack<ll> st;
for(ll v:vertex){
dp[v][0] = dp[v][1] = inf;
while(st.size() && !is_anc(st.top(),v)) st.pop();
if(st.size()){
vg[st.top()].pb({v,dist(v,st.top())});
vg[v].pb({st.top(),dist(v,st.top())});
}
st.push(v);
}
dfs(vertex.front(),vertex.front());
ll ans = inf;
for(ll v:vertex){
ans = min(ans,dp[v][0]+dp[v][1]);
}
for(ll v:vertex) vg[v].clear(),mark1[v] = mark2[v] = 0;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
47448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
47452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
47448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
