#include "factories.h"
#include <string.h>
#include <iostream>
#include <vector>
using namespace std;
vector<pair<int,int> > v[500005];
long long cum[500005];
bool del[500005];
int dep[500005],dp[20][500005],par[500005],sz[500005];
void dfs(int node,int p)
{
for (auto u:v[node])
{
if (u.first!=p)
{
dep[u.first]=dep[node]+1;
cum[u.first]=cum[node]+u.second;
dp[0][u.first]=node;
dfs(u.first,node);
}
}
}
int lca(int u,int v)
{
if (dep[u]<dep[v])
swap(u,v);
int d=dep[u]-dep[v];
for (int i=0;i<20;i++)
{
if (d&(1<<i))
u=dp[i][u];
}
if (u==v)
return u;
for (int i=19;i>=0;i--)
{
if (dp[i][u]!=dp[i][v])
{
u=dp[i][u];
v=dp[i][v];
}
}
return dp[0][u];
}
long long dist(int a,int b)
{
return cum[a]+cum[b]-2*cum[lca(a,b)];
}
void pre(int node,int p)
{
sz[node]=1;
for (auto u:v[node])
{
if (!del[u.first] && u.first!=p)
{
dfs(u.first,node);
sz[node]+=sz[u.first];
}
}
}
int find(int node,int p,int n)
{
for (auto u:v[node])
{
if (u.first!=p && !del[u.first] && sz[u.first]>n/2)
return find(u.first,node,n);
}
return node;
}
void dfs2(int node,int p)
{
pre(node,-1);
int c=find(node,-1,sz[node]);
par[c]=p;
del[c]=1;
for (auto u:v[c])
{
if (!del[u.first])
dfs2(u.first,c);
}
}
long long ans[500005];
void update(int node,bool mem)
{
int cur=node;
while (cur!=-1)
{
if (mem)
ans[cur]=(1LL<<60);
else
ans[cur]=min(ans[cur],dist(cur,node));
cur=par[cur];
}
}
long long query(int node)
{
int cur=node;
long long ret=(1LL<<60);
while (cur!=-1)
{
ret=min(ret,dist(cur,node)+ans[cur]);
cur=par[cur];
}
return ret;
}
void Init(int n,int a[],int b[],int d[])
{
for (int i=1;i<n;i++)
{
v[a[i]].push_back({b[i],d[i]});
v[b[i]].push_back({a[i],d[i]});
}
memset(dp,-1,sizeof(dp));
dfs(0,-1);
for (int i=1;i<20;i++)
{
for (int x=0;x<n;x++)
{
if (dp[i-1][x]!=-1)
dp[i][x]=dp[i-1][dp[i-1][x]];
}
}
/*dfs2(0,-1);
for (int i=0;i<n;i++)
update(i,1);*/
}
long long Query(int s,int x[],int t,int y[])
{
long long ret=(1LL<<60);
for (int i=0;i<s;i++)
{
for (int j=0;j<t;j++)
ret=min(ret,dist(x[i],y[j]));
}
return ret;
/*for (int i=0;i<s;i++)
update(x[i],0);
long long ret=(1LL<<60);
for (int i=0;i<t;i++)
ret=min(ret,query(y[i]));
for (int i=0;i<s;i++)
update(x[i],1);
return ret;*/
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
209 ms |
51448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
61 ms |
51556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
209 ms |
51448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
