This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define N 500500
#define pb push_back
struct GRAPH
{
int node;
long long weight;
};
int root;
int sz[N], pa[N], lv[N], jmp_node[20][N];
long long dis[N], jmp_dis[20][N], dp[20][N];
bool visit[N];
vector<GRAPH> g[N];
queue<int> bt;
int get_sz(int u, int p)
{
sz[u] = 1;
for(auto x : g[u])
if(x.node != p) sz[u] += get_sz(x.node, u);
return sz[u];
}
int get_centroid(int u, int p, int n)
{
bool ch = (n - sz[u] <= n/2) ? true : false;
int nu = 0, nf = 0;
for(auto x : g[u])
{
if(visit[x.node] || x.node == p) continue ;
if(sz[x.node] > n/2)
{
ch = false;
if(sz[x.node] > nf)
{
nf = sz[x.node];
nu = x.node;
}
}
}
return (ch) ? u : get_centroid(nu, u, n);
}
int build(int u, int p)
{
int c = get_centroid(u, p, get_sz(u, p));
visit[c] = true;
for(auto x : g[c])
{
if(visit[x.node]) continue ;
pa[build(x.node, c)] = c;
}
return c;
}
void dfs(int u, int l)
{
lv[u] = l;
for(auto x : g[u])
{
if(lv[x.node]) continue ;
jmp_node[0][x.node] = u;
jmp_dis[0][x.node] = x.weight;
dfs(x.node, l+1);
}
}
long long get_dis(int u, int v)
{
long long ret = 0;
if(lv[u] < lv[v]) swap(u, v);
for(int i=19 ; i>=0 ; i--)
if(lv[jmp_node[i][u]] >= lv[v])
{
ret += jmp_dis[i][u];
u = jmp_node[i][u];
}
if(u == v) return ret;
for(int i=19 ; i>=0 ; i--)
if(jmp_node[i][u] != jmp_node[i][v])
{
ret += jmp_dis[i][u] + jmp_dis[i][v];
u = jmp_node[i][u], v = jmp_node[i][v];
}
return ret + jmp_dis[0][u] + jmp_dis[0][v];
}
void Init(int n, int u[], int v[], int w[])
{
for(int i=0 ; i<n-1 ; i++)
{
g[u[i]+1].pb({v[i]+1, w[i]});
g[v[i]+1].pb({u[i]+1, w[i]});
}
dfs(1, 1);
build(1, 0);
for(int i=1 ; i<=n ; i++)
{
visit[i] = false;
dis[i] = 1e15;
}
for(int i=1 ; i<20 ; i++)
for(int j=1 ; j<=n ; j++)
{
jmp_node[i][j] = jmp_node[i-1][jmp_node[i-1][j]];
jmp_dis[i][j] = jmp_dis[i-1][j] + jmp_dis[i-1][jmp_node[i-1][j]];
}
for(int i=1 ; i<=n ; i++)
{
int now = i;
for(int j=0 ; true ; j++, now = pa[now])
{
if(!now) break ;
dp[j][i] = get_dis(i, now);
}
}
}
long long Query(int s, int x[], int t, int y[])
{
long long ans = 1e15;
for(int i=0 ; i<s ; i++)
{
int now = x[i]+1;
for(int j=0 ; true ; j++, now = pa[now])
{
if(!now) break ;
if(!visit[now])
{
visit[now] = true;
bt.push(now);
}
dis[now] = min(dis[now], dp[j][x[i]+1]);
}
}
for(int i=0 ; i<t ; i++)
{
int now = y[i]+1;
for(int j=0 ; true ; j++, now = pa[now])
{
if(!now) break ;
ans = min(ans, dis[now] + dp[j][y[i]+1]);
}
}
while(!bt.empty())
{
visit[bt.front()] = false;
dis[bt.front()] = 1e15;
bt.pop();
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |