#include "factories.h"
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
typedef pair<int,int> ppair;
ppair lev[500010];
int r,s,cnt,ch[500010],n,q,go[500010],num[500010],x,y,z,top[500010],len[500010];
long long dap=2147483647;
vector<int>con[500010];
vector<int>cost[500010];
vector<int>treeb[500010];
vector<int>trees[500010];
struct data{
int p,q,len;
}ch2[500010];
struct data2{
int x,cost;
}anc[500010];
void dfs(int x,int l)
{
int i;
ch[x]=1; lev[x].first=l; lev[x].second=x;
for(i=0;i<con[x].size();i++){
if(ch[con[x][i]]) continue;
anc[con[x][i]].x=x; anc[con[x][i]].cost=cost[x][i];
dfs(con[x][i],l+1);
num[x]+=num[con[x][i]];
}
num[x]++;
}
void dfs2(int x)
{
int i,maxi=-2147483647,p=-1;
ch2[x].p=cnt;
top[cnt]++; ch2[x].q=top[cnt]; go[x]=s;
for(i=0;i<con[x].size();i++){
if(ch2[con[x][i]].p==0 && maxi<num[con[x][i]]) maxi=num[con[x][i]], p=i;
}
if(p==-1) return;
ch2[con[x][p]].len=ch2[x].len+cost[x][p]; len[cnt]=ch2[x].len+cost[x][p];
dfs2(con[x][p]);
}
void Init(int n, int A[], int B[], int D[])
{
int i,j,t,c;
for(i=0;i<n-1;i++){
x=A[i]+1; y=B[i]+1; z=D[i];
con[x].push_back(y); con[y].push_back(x);
cost[x].push_back(z); cost[y].push_back(z);
}
dfs(1,1);
sort(lev+1,lev+n+1);
for(i=1;i<=n;i++){
t=lev[i].second;
if(!ch2[t].p){cnt++; s=t; dfs2(t);}
}
for(i=1;i<=cnt;i++){
for(c=1;c<=top[i];c*=2);
top[i]=c;
}
for(i=1;i<=cnt;i++){
for(j=0;j<=top[i]*2;j++){treeb[i].push_back(2147483647); trees[i].push_back(2147483647);}
}
}
void updateb(int p,int x,int val)
{
x+=top[p]-1; treeb[p][x]=val; x/=2;
while(x){
treeb[p][x]=min(treeb[p][x*2],treeb[p][x*2+1]);
x/=2;
}
}
void updates(int p,int x,int val)
{
x+=top[p]-1; trees[p][x]=val; x/=2;
while(x){
trees[p][x]=min(trees[p][x*2],trees[p][x*2+1]);
x/=2;
}
}
void pro1(int x,int sw)
{
int sum=0,p,q;
while(x){
p=ch2[x].p; q=ch2[x].q;
if(sw==0){
updateb(p,q,sum+len[p]-ch2[x].len);
updates(p,q,sum-len[p]+ch2[x].len);
}
else{
updateb(p,q,2147483647);
updates(p,q,2147483647);
}
sum+=ch2[x].len+anc[go[x]].cost;
x=anc[go[x]].x;
}
}
int queryb(int p,int x,int y,int k,int s,int e)
{
if(x>e || y<s) return 2147483647;
if(s<=x && y<=e) return treeb[p][k];
return min(queryb(p,x,(x+y)/2,k*2,s,e),queryb(p,(x+y)/2+1,y,k*2+1,s,e));
}
int querys(int p,int x,int y,int k,int s,int e)
{
if(x>e || y<s) return 2147483647;
if(s<=x && y<=e) return trees[p][k];
return min(querys(p,x,(x+y)/2,k*2,s,e),querys(p,(x+y)/2+1,y,k*2+1,s,e));
}
void pro2(int x)
{
int sum=0,p,q;
while(x){
p=ch2[x].p; q=ch2[x].q;
dap=min(dap,(long long)sum-len[p]+ch2[x].len+queryb(p,1,top[p],1,1,q));
dap=min(dap,(long long)sum+len[p]-ch2[x].len+querys(p,1,top[p],1,q,top[p]));
sum+=ch2[x].len+anc[go[x]].cost;
x=anc[go[x]].x;
}
}
long long Query(int S, int X[], int T, int Y[])
{
int i,j;
dap=2147483647;
for(i=0;i<S;i++) pro1(X[i]+1,0);
for(i=0;i<T;i++) pro2(Y[i]+1);
for(i=0;i<S;i++) pro1(X[i]+1,1);
return dap;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
93800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
93800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4503 ms |
161648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
