#include "factories.h"
#include "bits/stdc++.h"
#define MAXN 500009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,ll> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
vector<PII>adj[MAXN],gr[MAXN];
const int LOG=19;
int in[MAXN],out[MAXN],P[MAXN][LOG];
int col[MAXN],lvl[MAXN],T;
ll val[MAXN];
void dfs1(int nd,int pr){
in[nd]=++T;
tr(it,adj[nd])
if(it->ff!=pr){
val[it->ff]=val[nd]+it->ss;
lvl[it->ff]=lvl[nd]+1;
P[it->ff][0]=nd;
dfs1(it->ff,nd);
}
out[nd]=T;
}
void Init(int N, int A[], int B[], int D[]) {
for(int i=0;i<N-1;i++){
int u=A[i],v=B[i],w=D[i];
adj[u].pb(mp(v,w));
adj[v].pb(mp(u,w));
}
memset(col,-1,sizeof col);
memset(P,-1,sizeof P);
dfs1(0,-1);
for(int j=1;j<LOG;j++)
for(int i=0;i<N;i++)
if(~P[i][j-1])
P[i][j]=P[P[i][j-1]][j-1];
}
bool cmp(int x,int y){
return (in[x]<in[y]);
}
bool ata(int x,int y){
return (in[x]<=in[y] and out[y]<=out[x]);
}
int LCA(int x,int y){
if(lvl[x]<lvl[y])
swap(x,y);
for(int i=LOG-1;i>=0;i--)
if(~P[x][i] and lvl[P[x][i]]>=lvl[y])
x=P[x][i];
if(x==y)return x;
for(int i=LOG-1;i>=0;i--)
if(~P[x][i] and P[x][i]!=P[y][i])
x=P[x][i],y=P[y][i];
return P[x][0];
}
const ll B=1e15;
ll dp[MAXN][2],ans;
void dfs(int nd){
dp[nd][0]=dp[nd][1]=B;
if(~col[nd])dp[nd][col[nd]]=0;
tr(it,gr[nd]){
dfs(it->ff);
umin(dp[nd][0],dp[it->ff][0]+it->ss);
umin(dp[nd][1],dp[it->ff][1]+it->ss);
}
umin(ans,dp[nd][0]+dp[nd][1]);
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int>g;
for(int i=0;i<S;i++)
col[X[i]]=0,g.pb(X[i]);
for(int i=0;i<T;i++)
col[Y[i]]=1,g.pb(Y[i]);
sort(all(g),cmp);vector<int>v=g;
for(int i=0;i<int(g.size())-1;i++)
v.pb(LCA(g[i],g[i+1]));
sort(all(v));v.erase(unique(all(v)),v.end());
stack<int>st;int root=v[0];
tr(it,v){
while(!st.empty() and !ata(st.top(),*it))
st.pop();
if(!st.empty())
gr[st.top()].pb(mp(*it,val[*it]-val[st.top()]));
st.push(*it);
}
ans=B;dfs(root);
tr(it,v)gr[*it].clear();
for(int i=0;i<S;i++)
col[X[i]]=-1;
for(int i=0;i<T;i++)
col[Y[i]]=-1;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
63724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
63212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
63724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
