#include<bits/stdc++.h>
#include<factories.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;
const ll maxn = 5e5 + 16 , md = 1e9 + 7 , inf = 2e16;
ll n;
vector<pll> adj[maxn] , s , r;
vector<ll> v , vdj[maxn];
bitset<maxn> bl , rd;
ll jad[maxn][20] , dis[maxn] , dep = 0 , st[maxn] , ft[maxn] , tme = 0 , ps[maxn] , sum = 0 , bc[maxn] , rc[maxn];
void pDFS(ll r , ll par){
st[r] = tme++;
dis[r] = dep++;
ps[r] = sum;
jad[r][0] = par;
for(auto p : adj[r]){
ll i = p.first , w = p.second;
if(i == par) continue;
sum += w;
pDFS(i , r);
sum -= w;
}
ft[r] = tme;
dep--;
return;
}
ll find_jad(ll v , ll d){
d = dis[v] - d;
for(ll j = 0 ; j < 20 ; j++){
if(d & (1 << j)) v = jad[v][j];
}
return v;
}
ll lca(ll v , ll u){
if(dis[v] > dis[u]) swap(v , u);
u = find_jad(u , dis[v]);
if(v == u) return v;
for(ll j = 19 ; j >= 0 ; j--){
if(jad[v][j] != jad[u][j]){
v = jad[v][j];
u = jad[u][j];
}
}
return jad[v][0];
}
void Init(int N , int v[] , int u[] , int w[]){
memset(jad , -1 , sizeof(jad));
n = N;
for(ll i = 0 ; i < n - 1 ; i++){
adj[v[i]].push_back({u[i] , w[i]});
adj[u[i]].push_back({v[i] , w[i]});
}
pDFS(0 , -1);
return;
}
void cDFS(ll r){
for(auto i : vdj[r]){
cDFS(i);
rc[r] = min(rc[r] , rc[i]);
bc[r] = min(bc[r] , bc[i]);
}
if(rd[r]){
rc[r] = ps[r];
} else if(bl[r]){
bc[r] = ps[r];
}
return;
}
ll Query(int k1 , int v1[] , int k2 , int v2[]){
s.clear(); r.clear(); v.clear();
for(ll e = 0 ; e < k1 ; e++){
ll i = v1[e];
s.push_back({st[i] , i});
bl[i] = true;
}
for(ll e = 0 ; e < k2 ; e++){
ll i = v2[e];
s.push_back({st[i] , i});
rd[i] = true;
}
sort(all(s)); r = s;
ll sz = sze(s);
for(ll e = 1 ; e < sz ; e++){
ll i = s[e].second , j = s[e - 1].second , l = lca(i , j);
r.push_back({st[l] , l});
}
sort(all(r));
r.resize(distance(r.begin() , unique(all(r))));
// ll rs = sze(r);
// for(ll e = 0 ; e < rs ; e++){
// ll i = r[e].second , pr = -1;
// while(!v.empty()){
// ll u = v.back();
// if(st[u] < st[i] && ft[i] <= ft[u]){
// pr = u;
// break;
// }
// v.pop_back();
// }
// if(pr != -1) vdj[pr].push_back(i);
// v.push_back(i);
// }
// cDFS(v[0]);
// ll res = inf;
// for(ll e = 0 ; e < rs ; e++){
// ll i = r[e].second;
// res = min(res , bc[i] + rc[i] - 2ll * ps[i]);
// bc[i] = rc[i] = inf;
// bl[i] = rd[i] = false;
// vdj[i].clear();
// }
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
102340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
102212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
102340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
