#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n = 5e5 + 5,m,timer = 0;
vector<set<pair<int,int>>>adj(n);
vi sub(n),par(n,-1),in(n),out(n);
vl d(n),res(n,inf);
vi when(n);
int queryNumber;
vvi dp(n,vi(21,1));
void orig_dfs(int i,int p,ll w)
{
if (p != -1)d[i] = d[p] + w;
if (p != -1)dp[i][0] = p;
for (int power = 1;power<=20;power++)dp[i][power] = dp[dp[i][power - 1]][power - 1];
in[i] = ++timer;
for (auto val:adj[i]){
int c = val.first;
ll wt = val.second;
if (c != p)orig_dfs(c,i,wt);
}
out[i] = ++timer;
}
bool is_anc(int i,int j)
{
return in[i] <= in[j] && out[i] >= out[j];
}
int lca(int i,int j)
{
if (in[i] > in[j])swap(i,j);
int ret = j;
for (int power = 20;power >= 0;power--){
if (!is_anc(dp[ret][power],i))ret = dp[ret][power];
}
if (i == j)return i;
return dp[ret][0];
}
ll dist(int i,int j)
{
if (in[i] > in[j])swap(i,j);
int l = lca(i,j);
if (is_anc(i,j))return d[j] - d[i];
return d[i] + d[j] - 2 * d[l];
}
int dfs(int i,int p)
{
sub[i] = 1;
for (auto val:adj[i]){
int c = val.first;
if (c != p)sub[i] += dfs(c,i);
}
return sub[i];
}
int centroid(int i,int p,int sz)
{
for (auto val:adj[i]){
int c = val.first;
if (c != p && sub[c] > sz/2)return centroid(c,i,sz);
}
return i;
}
void decompose(int i,int p,ll w)
{
int cent = centroid(i,p,dfs(i,-1));
par[cent] = p;
for (auto val:adj[cent]){
int nxt = val.first;
ll wt = val.second;
adj[nxt].erase({cent,wt});
decompose(nxt,cent,wt);
}
}
void update(int i)
{
int cur = i;
while (cur != -1){
res[cur] = min(res[cur],dist(cur,i));
when[cur] = queryNumber;
cur = par[cur];
}
}
ll query(int i)
{
ll ret = inf;
int cur = i;
while (cur != -1){
ret = min(ret,dist(cur,i) + res[cur]);
cur = par[cur];
}
return ret;
}
void reset(int i)
{
while (i != -1){
res[i] = inf;
i = par[i];
}
}
void Init(int N, int a[], int b[], int d[]) {
n = N;
for (int i = 0;i<n - 1;i++){
int u = a[i],v = b[i],w = d[i];
u++,v++;
adj[u].insert({v,w}),adj[v].insert({u,w});
}
orig_dfs(1,-1,0);
decompose(1,-1,0);
update(1);
}
long long Query(int a, int v1[], int b, int v2[]) {
ll ans = inf;
for (int i = 0;i<a;i++)update(v1[i]);
for (int i = 0;i<b;i++)ans = min(ans,query(v2[i]));
for (int i = 0;i<a;i++)reset(v1[i]);
return ans;
}
// int main()
// {
// fast;
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// cin>>n>>m;
// for (int i = 0;i<n - 1;i++){int u,v,w;cin>>u>>v>>w;u++,v++;adj[u].insert({v,w}),adj[v].insert({u,w});}
// orig_dfs(1,-1,0);
// decompose(1,-1,0);
// update(1);
// while (m--){
// queryNumber++;
// int a,b;
// cin>>a>>b;
// ll ans = inf;
// vi all;
// for (int i = 1;i<=a;i++){int x;cin>>x;x++;update(x);all.pb(x);}
// for (int i = 1;i<=b;i++){int x;cin>>x;x++;ans = min(ans,query(x));}
// for (auto it:all)reset(it);
// cout<<ans<<'\n';
// }
// return 0;
// }
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
130 ms |
100424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
86 ms |
100168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
130 ms |
100424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
