QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#45441 | #4387. Static Query on Tree | miaomiaozi | AC ✓ | 90ms | 35452kb | C++17 | 5.1kb | 2022-08-23 21:24:53 | 2022-08-23 21:24:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
// https://space.bilibili.com/672346917
#ifndef LOCAL
#define LOG(...) 42
#endif
#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long LL;
typedef pair <int, int> PII;
constexpr int inf = 0x3f3f3f3f;
constexpr double EPS = 1e-8;
const double PI = acos(-1);
struct Tree {
int n, cnt, root;
vector <vector<int>> e;
vector <int> fa, dep, dfn, rnk, son, siz, top;
Tree() {}
Tree(int _n, int _r = 1) : n(_n + 1), e(n), cnt(0), root(_r),
fa(n), dep(n), dfn(n), rnk(n), son(n), siz(n), top(n) {
}
Tree(int _n, vector <vector<int>> &_e, int _r = 1) : n(_n + 1), e(_e), cnt(0), root(_r),
fa(n), dep(n), dfn(n), rnk(n), son(n), siz(n), top(n) {
init();
}
void init() {
dfs1(root, -1);
dfs2(root, root);
}
void add(int u, int v) {
e[u].push_back(v);
e[v].push_back(u);
}
void dfs1(int u, int father) {
siz[u] = 1, son[u] = -1;
for (int v : e[u]) {
if (v != father) {
fa[v] = u, dep[v] = dep[u] + 1;
dfs1(v, u);
siz[u] += siz[v];
if (son[u] == -1 || siz[v] > siz[son[u]])
son[u] = v;
}
}
}
void dfs2(int u, int t) {
dfn[u] = ++cnt;
rnk[cnt] = u, top[u] = t;
if (son[u] == -1) return;
dfs2(son[u], t);
for (int v : e[u])
if (v != fa[u] && v != son[u])
dfs2(v, v);
}
int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
}
return dep[u] < dep[v] ? u : v;
}
template <typename T>
T query(int u, int v, function <T(int, int)> func) {
T ret = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ret += func(dfn[top[u]], dfn[u]);
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap(u, v);
ret += func(dfn[v], dfn[u]);
return ret;
}
void modify(int u, int v, function <void(int, int)> func) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
func(dfn[top[u]], dfn[u]);
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap(u, v);
func(dfn[v], dfn[u]);
}
vector <PII> get_interval(int u, int v) {
vector <PII> res;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
res.pb({dfn[top[u]], dfn[u]});
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap(u, v);
res.pb({dfn[v], dfn[u]});
return res;
}
};
int multi_cases = 1;
void A_SOUL_AvA () {
int n, q;
cin >> n >> q;
vector <vector<int>> e(n + 1);
for (int i = 2; i <= n; i++) {
int fa;
cin >> fa;
e[fa].pb(i);
}
Tree tr(n, e, 1);
auto dfn = tr.dfn, siz = tr.siz;
auto gao = [&](int x, vector <PII> &a) {
auto v = tr.get_interval(x, 1);
for (auto &j : v) {
a.pb(j);
}
};
auto merge = [&](vector <PII> &segs) {
vector <PII> res;
if (segs.empty()) return res;
segs.push_back({1e9, 1e9});
sort(segs.begin(), segs.end());
auto [L, R] = segs[0];
for (auto [l, r] : segs) {
if (l > R) {
res.pb({L, R});
L = l, R = r;
} else {
R = max(R, r);
}
}
return res;
};
auto interset = [&](vector <PII> a, vector <PII> b) {
vector <PII> res;
int n = a.size(), m = b.size();
for (int i = 0, j = 0; i < n && j < m; ) {
int l = max(a[i].fi, b[j].fi);
int r = min(a[i].se, b[j].se);
if (l <= r) {
res.pb({l, r});
}
if (a[i].se < b[j].se) i++;
else j++;
}
return res;
};
while (q--) {
int A, B, C;
cin >> A >> B >> C;
vector <PII> a, b, c;
for (int i = 0, x; i < A; i++) {
cin >> x;
gao(x, a);
}
for (int i = 0, x; i < B; i++) {
cin >> x;
gao(x, b);
}
for (int i = 0, x; i < C; i++) {
cin >> x;
c.pb({dfn[x], dfn[x] + siz[x] - 1});
}
a = merge(a), b = merge(b), c = merge(c);
auto tot = interset(interset(a, b), c);
LL ans = 0;
for (auto [l, r] : tot) {
ans += r - l + 1;
}
cout << ans << endl;
}
}
int main () {
cin.tie(nullptr)->sync_with_stdio(false);
cout << fixed << setprecision(12);
int T = 1;
for (multi_cases && cin >> T; T; T--) {
A_SOUL_AvA ();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 90ms
memory: 35452kb
input:
1 200000 18309 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
output:
102147 62590 87270 88880 7654 61542 62953 85022 55135 54125 70500 64356 25824 88300 42278 15336 18132 28734 90282 42889 28099 31311 96842 19959 34366 60205 78358 91142 56048 74688 86091 51979 94750 11989 89544 86860 56720 29534 52343 90031 79002 90293 94554 48340 65015 9181 15016 19884 49445 14181 6...
result:
ok 18309 numbers