#include "factories.h"
#define pb push_back
#define ar array
const int NN = 5e5 + 5;
int n,m,k;
struct Bit {
int sz;
vector<long long> t, bn;
Bit (int n){
this->sz = n;
t.resize(sz * 4);
bn.resize(sz * 4);
for(int i = 0;i<sz*4;i++)bn[i] = -1;
}
void push(int tl, int tr, int v){
if(bn[v] == -1)return;
if(tl != tr){
bn[v*2] = bn[v];
bn[v*2+1] = bn[v];
}
t[v] = (tr - tl + 1) * bn[v];
bn[v] = -1;
}
void update(int tl, int tr, int v, int l, int r, int val){
push(tl, tr, v);
if(r < l || tr < l || r < tl)return;
if(l <= tl && tr <= r){
bn[v] = val;
push(tl, tr, v);
return;
}
int tm = (tl + tr) / 2;
update(tl, tm, v*2, l, r, val); update(tm+1, tr, v*2+1, l, r, val);
t[v] = t[v*2] + t[v*2+1];
}
void upd(int l, int r, int x){
update(1, n, 1, l, r, x);
}
int gt(int tl, int tr, int v, int l, int r){
push(tl, tr, v);
if(r < l || tr < l || r < tl)return 0ll;
if(l <= tl && tr <= r){
return t[v];
}
int tm = (tl + tr) / 2;
int a = gt(tl, tm, v*2, l, r);
int b = gt(tm+1, tr, v*2+1, l, r);
t[v] = t[v*2] + t[v*2+1];
return a + b;
}
int get(int l, int r){
return gt(1, n, 1, l, r);
}
};
Bit t(NN);
vector<ar<long long,2>>g[NN];
vector<long long>id(NN), head(NN), id_(NN), p(NN), sz(NN), dep(NN);
int timer, sum;
void dfs(int x, int pr){
p[x] = pr;
sz[x] = 1;
for(auto [to, dist] : g[x]){
if(to == pr)continue;
dep[to] = dep[x] + dist;
dfs(to, x);
sz[x] += sz[to];
}
}
void hld(int x, int pr){
int hv = -1;
timer += 1; id[x] = timer; id_[timer] = x;
for(auto [to, dist] : g[x]){
if(to == pr)continue;
if(hv == -1 || sz[hv] < sz[to])hv = to;
}
if(hv != -1){
head[hv] = head[x];
hld(hv, x);
}
for(auto [to, dist] : g[x]){
if(to == pr || to == hv)continue;
head[to] = to;
hld(to, x);
}
}
int up(int x){
if(t.get(id[x], id[x]) > 0)return x;
int h = head[x];
if(t.get(id[h], id[x]) == 0){
if(p[h] == h)return h;
else return up(p[h]);
}
for(int i = 19;i>=0;i--){
int num = id[x] - (1ll << i);
if(num < id[h])continue;
int node = id_[num];
if(t.get(num, id[x]) == 0){
x = node;
}
}
return p[x];
}
void root(int x){
int h = head[x];
t.upd(id[h], id[x], 1);
if(h == 0)return;
root(p[h]);
}
void root2(int x){
int h = head[x];
t.upd(id[h], id[x], 0);
if(h == 0)return;
root2(p[h]);
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for(int i = 0;i<n;i++){
g[A[i]].pb({B[i], D[i]});
g[B[i]].pb({A[i], D[i]});
}
dfs(0, 0);
head[0] = 0;
hld(0, 0);
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i = 0;i<S;i++){
root(X[i]);
}
vector<ar<long long,2>>vs;
for(int i = 0;i<T;i++){
int u = up(Y[i]);
vs.pb({u, dep[Y[i]] - dep[u]});
}
for(int i = 0;i<S;i++){
root2(X[i]);
}
sort(vs.begin(), vs.end());
for(int i = 0;i<vs.size();i++){
if(i == vs.size() - 1 || vs[i+1][0] != vs[i][0]){
t.upd(id[vs[i][0]], id[vs[i][0]], vs[i][1]);
continue;
}
vs[i+1][1] = min(vs[i+1][1], vs[i][1]);
}
long long res = 1e17 + 7;
for(int i = 0;i<S;i++){
int u = up(X[i]);
if(t.get(id[u], id[u]) == 0)continue;
// cout << u << " " << X[i] << " " << t.get(id[u], id[u]) << " ";
res = min(res, dep[X[i]] - dep[u] + t.get(id[u], id[u]));
}
for(auto [x, u] : vs){
t.upd(id[x], id[x], 0);
}
return res;
}
Compilation message (stderr)
factories.cpp:11:5: error: 'vector' does not name a type
11 | vector<long long> t, bn;
| ^~~~~~
factories.cpp: In constructor 'Bit::Bit(int)':
factories.cpp:14:9: error: 't' was not declared in this scope; did you mean 'gt'?
14 | t.resize(sz * 4);
| ^
| gt
factories.cpp:15:9: error: 'bn' was not declared in this scope; did you mean 'n'?
15 | bn.resize(sz * 4);
| ^~
| n
factories.cpp: In member function 'void Bit::push(int, int, int)':
factories.cpp:20:12: error: 'bn' was not declared in this scope; did you mean 'n'?
20 | if(bn[v] == -1)return;
| ^~
| n
factories.cpp:22:17: error: 'bn' was not declared in this scope; did you mean 'n'?
22 | bn[v*2] = bn[v];
| ^~
| n
factories.cpp:25:9: error: 't' was not declared in this scope; did you mean 'gt'?
25 | t[v] = (tr - tl + 1) * bn[v];
| ^
| gt
factories.cpp:25:32: error: 'bn' was not declared in this scope; did you mean 'n'?
25 | t[v] = (tr - tl + 1) * bn[v];
| ^~
| n
factories.cpp: In member function 'void Bit::update(int, int, int, int, int, int)':
factories.cpp:33:17: error: 'bn' was not declared in this scope; did you mean 'n'?
33 | bn[v] = val;
| ^~
| n
factories.cpp:39:9: error: 't' was not declared in this scope; did you mean 'gt'?
39 | t[v] = t[v*2] + t[v*2+1];
| ^
| gt
factories.cpp: In member function 'int Bit::gt(int, int, int, int, int)':
factories.cpp:50:24: error: 't' was not declared in this scope; did you mean 'gt'?
50 | return t[v];
| ^
| gt
factories.cpp:55:9: error: 't' was not declared in this scope; did you mean 'gt'?
55 | t[v] = t[v*2] + t[v*2+1];
| ^
| gt
factories.cpp: At global scope:
factories.cpp:4:12: error: 'array' was not declared in this scope
4 | #define ar array
| ^~~~~
factories.cpp:67:8: note: in expansion of macro 'ar'
67 | vector<ar<long long,2>>g[NN];
| ^~
factories.cpp:4:12: error: 'array' was not declared in this scope
4 | #define ar array
| ^~~~~
factories.cpp:67:8: note: in expansion of macro 'ar'
67 | vector<ar<long long,2>>g[NN];
| ^~
factories.cpp:4:12: error: 'array' was not declared in this scope
4 | #define ar array
| ^~~~~
factories.cpp:67:8: note: in expansion of macro 'ar'
67 | vector<ar<long long,2>>g[NN];
| ^~
factories.cpp:4:12: error: 'array' was not declared in this scope
4 | #define ar array
| ^~~~~
factories.cpp:67:8: note: in expansion of macro 'ar'
67 | vector<ar<long long,2>>g[NN];
| ^~
factories.cpp:4:12: error: 'array' was not declared in this scope
4 | #define ar array
| ^~~~~
factories.cpp:67:8: note: in expansion of macro 'ar'
67 | vector<ar<long long,2>>g[NN];
| ^~
factories.cpp:4:12: error: 'array' was not declared in this scope
4 | #define ar array
| ^~~~~
factories.cpp:67:8: note: in expansion of macro 'ar'
67 | vector<ar<long long,2>>g[NN];
| ^~
factories.cpp:4:12: error: 'array' was not declared in this scope
4 | #define ar array
| ^~~~~
factories.cpp:67:8: note: in expansion of macro 'ar'
67 | vector<ar<long long,2>>g[NN];
| ^~
factories.cpp:4:12: error: 'array' was not declared in this scope
4 | #define ar array
| ^~~~~
factories.cpp:67:8: note: in expansion of macro 'ar'
67 | vector<ar<long long,2>>g[NN];
| ^~
factories.cpp:4:12: error: 'array' was not declared in this scope
4 | #define ar array
| ^~~~~
factories.cpp:67:8: note: in expansion of macro 'ar'
67 | vector<ar<long long,2>>g[NN];
| ^~
factories.cpp:67:1: error: 'vector' does not name a type
67 | vector<ar<long long,2>>g[NN];
| ^~~~~~
factories.cpp:68:1: error: 'vector' does not name a type
68 | vector<long long>id(NN), head(NN), id_(NN), p(NN), sz(NN), dep(NN);
| ^~~~~~
factories.cpp: In function 'void dfs(int, int)':
factories.cpp:72:9: error: 'p' was not declared in this scope
72 | p[x] = pr;
| ^
factories.cpp:73:9: error: 'sz' was not declared in this scope
73 | sz[x] = 1;
| ^~
factories.cpp:75:31: error: 'g' was not declared in this scope
75 | for(auto [to, dist] : g[x]){
| ^
factories.cpp:77:17: error: 'dep' was not declared in this scope
77 | dep[to] = dep[x] + dist;
| ^~~
factories.cpp: In function 'void hld(int, int)':
factories.cpp:85:21: error: 'id' was not declared in this scope
85 | timer += 1; id[x] = timer; id_[timer] = x;
| ^~
factories.cpp:85:36: error: 'id_' was not declared in this scope
85 | timer += 1; id[x] = timer; id_[timer] = x;
| ^~~
factories.cpp:87:31: error: 'g' was not declared in this scope
87 | for(auto [to, dist] : g[x]){
| ^
factories.cpp:89:32: error: 'sz' was not declared in this scope
89 | if(hv == -1 || sz[hv] < sz[to])hv = to;
| ^~
factories.cpp:93:17: error: 'head' was not declared in this scope
93 | head[hv] = head[x];
| ^~~~
factories.cpp:97:31: error: 'g' was not declared in this scope
97 | for(auto [to, dist] : g[x]){
| ^
factories.cpp:99:17: error: 'head' was not declared in this scope
99 | head[to] = to;
| ^~~~
factories.cpp: In function 'int up(int)':
factories.cpp:105:18: error: 'id' was not declared in this scope
105 | if(t.get(id[x], id[x]) > 0)return x;
| ^~
factories.cpp:107:17: error: 'head' was not declared in this scope
107 | int h = head[x];
| ^~~~
factories.cpp:108:18: error: 'id' was not declared in this scope
108 | if(t.get(id[h], id[x]) == 0){
| ^~
factories.cpp:109:20: error: 'p' was not declared in this scope
109 | if(p[h] == h)return h;
| ^
factories.cpp:114:27: error: 'id' was not declared in this scope; did you mean 'i'?
114 | int num = id[x] - (1ll << i);
| ^~
| i
factories.cpp:116:28: error: 'id_' was not declared in this scope
116 | int node = id_[num];
| ^~~
factories.cpp:122:16: error: 'p' was not declared in this scope
122 | return p[x];
| ^
factories.cpp: In function 'void root(int)':
factories.cpp:126:17: error: 'head' was not declared in this scope
126 | int h = head[x];
| ^~~~
factories.cpp:127:15: error: 'id' was not declared in this scope
127 | t.upd(id[h], id[x], 1);
| ^~
factories.cpp:129:14: error: 'p' was not declared in this scope
129 | root(p[h]);
| ^
factories.cpp: In function 'void root2(int)':
factories.cpp:133:17: error: 'head' was not declared in this scope
133 | int h = head[x];
| ^~~~
factories.cpp:134:15: error: 'id' was not declared in this scope
134 | t.upd(id[h], id[x], 0);
| ^~
factories.cpp:136:15: error: 'p' was not declared in this scope
136 | root2(p[h]);
| ^
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:142:17: error: 'g' was not declared in this scope
142 | g[A[i]].pb({B[i], D[i]});
| ^
factories.cpp:147:9: error: 'head' was not declared in this scope
147 | head[0] = 0;
| ^~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:4:12: error: 'array' was not declared in this scope
4 | #define ar array
| ^~~~~
factories.cpp:157:16: note: in expansion of macro 'ar'
157 | vector<ar<long long,2>>vs;
| ^~
factories.cpp:157:9: error: 'vector' was not declared in this scope
157 | vector<ar<long long,2>>vs;
| ^~~~~~
factories.cpp:157:19: error: expected primary-expression before 'long'
157 | vector<ar<long long,2>>vs;
| ^~~~
factories.cpp:160:17: error: 'vs' was not declared in this scope
160 | vs.pb({u, dep[Y[i]] - dep[u]});
| ^~
factories.cpp:160:27: error: 'dep' was not declared in this scope
160 | vs.pb({u, dep[Y[i]] - dep[u]});
| ^~~
factories.cpp:167:14: error: 'vs' was not declared in this scope
167 | sort(vs.begin(), vs.end());
| ^~
factories.cpp:167:9: error: 'sort' was not declared in this scope; did you mean 'short'?
167 | sort(vs.begin(), vs.end());
| ^~~~
| short
factories.cpp:170:31: error: 'id' was not declared in this scope; did you mean 'i'?
170 | t.upd(id[vs[i][0]], id[vs[i][0]], vs[i][1]);
| ^~
| i
factories.cpp:173:30: error: 'min' was not declared in this scope
173 | vs[i+1][1] = min(vs[i+1][1], vs[i][1]);
| ^~~
factories.cpp:179:26: error: 'id' was not declared in this scope; did you mean 'i'?
179 | if(t.get(id[u], id[u]) == 0)continue;
| ^~
| i
factories.cpp:181:32: error: 'dep' was not declared in this scope
181 | res = min(res, dep[X[i]] - dep[u] + t.get(id[u], id[u]));
| ^~~
factories.cpp:181:59: error: 'id' was not declared in this scope; did you mean 'i'?
181 | res = min(res, dep[X[i]] - dep[u] + t.get(id[u], id[u]));
| ^~
| i
factories.cpp:181:23: error: 'min' was not declared in this scope
181 | res = min(res, dep[X[i]] - dep[u] + t.get(id[u], id[u]));
| ^~~
factories.cpp:185:23: error: 'id' was not declared in this scope
185 | t.upd(id[x], id[x], 0);
| ^~