#include <stdlib.h>
#include <vector>
#include "factories.h"
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair <ll, ll> pll;
int IT_MAX = 1 << 17;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
bool dchk[500050];
int dep[500050];
int lr[500050][2];
ll par[500050][20][2];
int tus;
vector <pll> conn[500050];
void DFS(int n) {
dchk[n] = true;
lr[n][0] = ++tus;
for (auto it : conn[n]) {
if (dchk[it.second]) continue;
par[it.second][0][0] = n, par[it.second][0][1] = it.first;
for (int i = 1; i <= 18; i++) {
int tp = par[it.second][i - 1][0];
par[it.second][i][0] = par[tp][i - 1][0];
par[it.second][i][1] = par[it.second][i - 1][1] + par[tp][i - 1][1];
}
dep[it.second] = dep[n] + 1;
DFS(it.second);
}
lr[n][1] = tus;
}
pll lca(int a, int b) {
ll rv = 0;
if (dep[a] > dep[b]) swap(a, b);
int c = dep[b] - dep[a];
for (int i = 18; i >= 0; i--) {
if (c & (1 << i)) {
rv += par[b][i][1];
b = par[b][i][0];
}
}
if (a == b) return pll(rv, a);
for (int i = 18; i >= 0; i--) {
if (par[a][i][0] != par[b][i][0]) {
rv += par[a][i][1];
rv += par[b][i][1];
a = par[a][i][0];
b = par[b][i][0];
}
}
rv += par[a][0][1];
rv += par[b][0][1];
return pll(rv, par[a][0][0]);
}
void Init(int N, int A[], int B[], int D[]) {
int i, j;
for (i = 0; i <= N - 2; i++) {
conn[A[i]].emplace_back(D[i], B[i]);
conn[B[i]].emplace_back(D[i], A[i]);
}
tus = 0;
DFS(0);
}
class Node {
public:
ll mn, v;
Node() {
*this = Node(0, 0);
}
Node(ll mn, ll v) : mn(mn), v(v) {}
};
Node indt[1100000];
void update(int st, int en, int S, int E, int n, ll v) {
if (st > en) return;
if (st == S && en == E) {
indt[n].mn += v;
indt[n].v += v;
return;
}
int M = (S + E) / 2;
update(st, min(en, M), S, M, 2 * n, v);
update(max(M + 1, st), en, M + 1, E, 2 * n + 1, v);
indt[n].mn = min(indt[2 * n].mn, indt[2 * n + 1].mn) + indt[n].v;
}
ll qans;
vector <int> Vv;
vector <int> Vv2;
vector <pll> conn2[500050];
vector <pll> son2[500050];
ll dis[500050];
int lr2[500050][2];
int tchk[500050];
void DFS2(int n) {
dchk[n] = true;
lr2[n][0] = ++tus;
for (auto it : conn2[n]) {
if (dchk[it.second]) continue;
son2[n].push_back(it);
dis[it.second] = dis[n] + it.first;
DFS2(it.second);
}
lr2[n][1] = tus;
}
void DFS3(int n) {
if (tchk[n] == 1) qans = min(qans, indt[1].mn);
for (auto it : son2[n]) {
indt[1].mn += it.first, indt[1].v += it.first;
update(lr2[it.second][0], lr2[it.second][1], 1, IT_MAX, 1, -2 * it.first);
DFS3(it.second);
indt[1].mn -= it.first, indt[1].v -= it.first;
update(lr2[it.second][0], lr2[it.second][1], 1, IT_MAX, 1, 2 * it.first);
}
}
long long Query(int S, int X[], int T, int Y[]) {
Vv.reserve(2 * (S + T));
Vv2.reserve(S + T);
int i, j;
for (i = 0; i < S; i++) Vv.push_back(X[i]);
for (i = 0; i < T; i++) Vv.push_back(Y[i]);
sort(all(Vv), [](int a, int b) {
return lr[a][0] < lr[b][0];
});
for (i = 0; i + 1 < Vv.size(); i++) Vv2.push_back(lca(Vv[i], Vv[i + 1]).second);
for (auto it : Vv2) Vv.push_back(it);
sort(all(Vv), [](int a, int b) {
return lr[a][0] < lr[b][0];
});
Vv.erase(unique(all(Vv)), Vv.end());
for (auto it : Vv) tchk[it] = 0;
for (i = 0; i < S; i++) tchk[X[i]] = 1;
for (i = 0; i < T; i++) tchk[Y[i]] = -1;
for (i = 0; i + 1 < Vv.size(); i++) {
int x = Vv[i];
int y = Vv[i + 1];
x = lca(x, y).second;
pll u = lca(x, y);
conn2[x].emplace_back(u.first, y);
conn2[y].emplace_back(u.first, x);
}
for (i = 0; i < Vv.size(); i++) {
dchk[Vv[i]] = false;
dis[Vv[i]] = 0;
}
tus = 0;
DFS2(Vv[0]);
for (IT_MAX = 2; IT_MAX < Vv.size(); IT_MAX *= 2);
for (i = 1; i < 2 * IT_MAX; i++) indt[i] = Node(0, 0);
for (i = 0; i < Vv.size(); i++) {
ll v = dis[Vv[i]];
if (tchk[Vv[i]] != -1) v = LL_INF;
update(lr2[Vv[i]][0], lr2[Vv[i]][0], 1, IT_MAX, 1, v);
}
update(Vv.size() + 1, IT_MAX, 1, IT_MAX, 1, LL_INF);
qans = LL_INF;
DFS3(Vv[0]);
for (auto it : Vv) {
conn2[it].clear();
son2[it].clear();
}
Vv.clear();
Vv2.clear();
return qans;
}
Compilation message
factories.cpp:8:9: error: 'pair' does not name a type
typedef pair <ll, ll> pll;
^
factories.cpp:18:1: error: 'vector' does not name a type
vector <pll> conn[500050];
^
factories.cpp: In function 'void DFS(int)':
factories.cpp:22:17: error: 'conn' was not declared in this scope
for (auto it : conn[n]) {
^
factories.cpp: At global scope:
factories.cpp:35:1: error: 'pll' does not name a type
pll lca(int a, int b) {
^
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:62:3: error: 'conn' was not declared in this scope
conn[A[i]].emplace_back(D[i], B[i]);
^
factories.cpp:60:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
factories.cpp: In function 'void update(int, int, int, int, int, ll)':
factories.cpp:88:22: error: 'min' was not declared in this scope
update(st, min(en, M), S, M, 2 * n, v);
^
factories.cpp:88:22: note: suggested alternative:
In file included from /usr/include/c++/5/vector:60:0,
from factories.cpp:2:
/usr/include/c++/5/bits/stl_algobase.h:243:5: note: 'std::min'
min(const _Tp& __a, const _Tp& __b, _Compare __comp)
^
factories.cpp:89:22: error: 'max' was not declared in this scope
update(max(M + 1, st), en, M + 1, E, 2 * n + 1, v);
^
factories.cpp:89:22: note: suggested alternative:
In file included from /usr/include/c++/5/vector:60:0,
from factories.cpp:2:
/usr/include/c++/5/bits/stl_algobase.h:265:5: note: 'std::max'
max(const _Tp& __a, const _Tp& __b, _Compare __comp)
^
factories.cpp: At global scope:
factories.cpp:94:1: error: 'vector' does not name a type
vector <int> Vv;
^
factories.cpp:95:1: error: 'vector' does not name a type
vector <int> Vv2;
^
factories.cpp:96:1: error: 'vector' does not name a type
vector <pll> conn2[500050];
^
factories.cpp:97:1: error: 'vector' does not name a type
vector <pll> son2[500050];
^
factories.cpp: In function 'void DFS2(int)':
factories.cpp:104:17: error: 'conn2' was not declared in this scope
for (auto it : conn2[n]) {
^
factories.cpp:106:3: error: 'son2' was not declared in this scope
son2[n].push_back(it);
^
factories.cpp: In function 'void DFS3(int)':
factories.cpp:113:47: error: 'min' was not declared in this scope
if (tchk[n] == 1) qans = min(qans, indt[1].mn);
^
factories.cpp:113:47: note: suggested alternative:
In file included from /usr/include/c++/5/vector:60:0,
from factories.cpp:2:
/usr/include/c++/5/bits/stl_algobase.h:243:5: note: 'std::min'
min(const _Tp& __a, const _Tp& __b, _Compare __comp)
^
factories.cpp:114:17: error: 'son2' was not declared in this scope
for (auto it : son2[n]) {
^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:123:2: error: 'Vv' was not declared in this scope
Vv.reserve(2 * (S + T));
^
factories.cpp:124:2: error: 'Vv2' was not declared in this scope
Vv2.reserve(S + T);
^
factories.cpp:130:3: error: 'sort' was not declared in this scope
});
^
factories.cpp:132:72: error: 'lca' was not declared in this scope
for (i = 0; i + 1 < Vv.size(); i++) Vv2.push_back(lca(Vv[i], Vv[i + 1]).second);
^
factories.cpp:133:17: error: unable to deduce 'auto&&' from 'Vv2'
for (auto it : Vv2) Vv.push_back(it);
^
factories.cpp:137:25: error: 'unique' was not declared in this scope
Vv.erase(unique(all(Vv)), Vv.end());
^
factories.cpp:138:17: error: unable to deduce 'auto&&' from 'Vv'
for (auto it : Vv) tchk[it] = 0;
^
factories.cpp:145:15: error: 'lca' was not declared in this scope
x = lca(x, y).second;
^
factories.cpp:146:3: error: 'pll' was not declared in this scope
pll u = lca(x, y);
^
factories.cpp:147:3: error: 'conn2' was not declared in this scope
conn2[x].emplace_back(u.first, y);
^
factories.cpp:147:25: error: 'u' was not declared in this scope
conn2[x].emplace_back(u.first, y);
^
factories.cpp:169:17: error: unable to deduce 'auto&&' from 'Vv'
for (auto it : Vv) {
^
factories.cpp:170:3: error: 'conn2' was not declared in this scope
conn2[it].clear();
^
factories.cpp:171:3: error: 'son2' was not declared in this scope
son2[it].clear();
^
factories.cpp:125:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
