QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#90592 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | Rainybunny | 0 | 20ms | 20344kb | C++23 | 6.1kb | 2023-03-23 20:36:24 | 2023-03-23 20:36:25 |
Judging History
answer
/*+Rainybunny+*/
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)
typedef std::pair<int, int> PII;
#define fi first
#define se second
inline char fgc() {
static char buf[1 << 17], *p = buf, *q = buf;
return p == q && (q = buf + fread(p = buf, 1, 1 << 17, stdin), p == q)
? EOF : *p++;
}
template <typename Tp = int>
inline Tp rint() {
Tp x = 0, s = fgc(), f = 1;
for (; s < '0' || '9' < s; s = fgc()) f = s == '-' ? -f : f;
for (; '0' <= s && s <= '9'; s = fgc()) x = x * 10 + (s ^ '0');
return x * f;
}
template <typename Tp>
inline void wint(Tp x) {
if (x < 0) putchar('-'), x = -x;
if (9 < x) wint(x / 10);
putchar(x % 10 ^ '0');
}
const int MAXN = 2e5;
int n, q, fa[MAXN + 5], rad[MAXN + 5], ans[MAXN + 5];
std::vector<int> adj[MAXN + 5];
namespace V {
int dep[MAXN + 5], rt[MAXN + 5], siz[MAXN + 5], son[MAXN + 5], top[MAXN + 5];
struct Query { int r, k, id; };
std::vector<Query> qry[MAXN + 5];
struct SegmentTree {
static const int MAXND = 4e6; // !
int node, ch[MAXND][2], siz[MAXND];
inline void insert(int& u, const int l, const int r, const int x) {
if (!u) u = ++node;
++siz[u];
if (l == r) return ;
int mid = l + r >> 1;
if (x <= mid) insert(ch[u][0], l, mid, x);
else insert(ch[u][1], mid + 1, r, x);
}
inline int merge(const int u, const int v) {
if (!u || !v) return u | v;
int w = ++node; siz[w] = siz[u] + siz[v];
ch[w][0] = merge(ch[u][0], ch[v][0]);
ch[w][1] = merge(ch[u][1], ch[v][1]);
return w;
}
inline int query(const int u, const int l, const int r,
const int ql, const int qr) const {
if (!u) return 0;
if (ql <= l && r <= qr) return siz[u];
int mid = l + r >> 1, ret = 0;
if (ql <= mid) ret += query(ch[u][0], l, mid, ql, qr);
if (mid < qr) ret += query(ch[u][1], mid + 1, r, ql, qr);
return ret;
}
} sgt;
inline void init(const int u) {
siz[u] = 1, dep[u] = dep[fa[u]] + 1;
sgt.insert(rt[u], 1, n, dep[u]);
for (int v: adj[u]) if (v != fa[u]) {
fa[v] = u, init(v), siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
rt[u] = sgt.merge(rt[u], rt[v]);
}
}
inline void reorder(const int u, const int tp) {
top[u] = tp;
if (son[u]) reorder(son[u], tp);
for (int v: adj[u]) if (v != fa[u] && v != son[u]) reorder(v, v);
}
inline int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) v = fa[top[v]];
else u = fa[top[u]];
}
return dep[u] < dep[v] ? u : v;
}
inline void hang(int u, const int k, const int id) {
int las = 0;
while (u) {
qry[u].push_back({ rad[id], k, id });
if (son[u] && rad[id]) {
ans[id] += k * sgt.query(rt[son[u]], 1, n,
dep[son[u]], dep[son[u]] + rad[id] - 1);
}
if (las && rad[id]) {
ans[id] -= k * sgt.query(rt[las], 1, n,
dep[las], dep[las] + rad[id] - 1);
}
u = fa[las = top[u]];
}
}
struct BIT {
int val[MAXN + 5];
inline void add(int x, const int k) {
for (; x <= n; x += x & -x) val[x] += k;
}
inline int sum(int x) {
int ret = 0;
for (; x; x ^= x & -x) ret += val[x];
return ret;
}
} bit;
inline void collect(const int u, const int d, const int k) {
bit.add(d, k);
for (int v: adj[u]) if (v != fa[u]) collect(v, d + 1, k);
}
inline void solve(const int u) {
bit.add(1, 1);
for (int v: adj[u]) if (v != fa[u] && v != son[u]) collect(v, 2, 1);
for (auto [r, k, id]: qry[u]) ans[id] += k * bit.sum(r);
if (son[u]) solve(son[u]);
bit.add(1, -1);
for (int v: adj[u]) if (v != fa[u] && v != son[u]) collect(v, 2, -1);
}
} // namespace V
namespace R {
int siz[MAXN + 5], wgt[MAXN + 5], mxh, suh, sum[MAXN + 5], sub[MAXN + 5];
bool vis[MAXN + 5];
std::vector<int> qry[MAXN + 5];
inline void findG(const int u, const int fa, const int all, int& rt) {
siz[u] = 1, wgt[u] = 0;
for (int v: adj[u]) if (v != fa && !vis[v]) {
findG(v, u, all, rt), siz[u] += siz[v];
wgt[u] = std::max(wgt[u], siz[v]);
}
wgt[u] = std::max(wgt[u], all - siz[u]);
if (!rt || wgt[rt] > wgt[u]) rt = u;
}
inline void collect(const int u, const int fa, int* buc, int& h, const int d) {
++buc[d], h = std::max(h, d);
for (int v: adj[u]) if (v != fa && !vis[v]) collect(v, u, buc, h, d + 1);
}
inline void contri(const int u, const int fa, const int d) {
for (int id: qry[u]) if (rad[id] >= d) {
ans[id] += sum[std::min(rad[id] - d, mxh)];
ans[id] -= sub[std::min(rad[id] - d, suh)];
}
for (int v: adj[u]) if (v != fa && !vis[v]) contri(v, u, d + 1);
}
inline void solve(const int u) {
vis[u] = true;
collect(u, 0, sum, mxh = 0, 0);
rep (i, 1, mxh) sum[i] += sum[i - 1];
for (int id: qry[u]) ans[id] += sum[std::min(rad[id], mxh)];
for (int v: adj[u]) if (!vis[v]) {
collect(v, 0, sub, suh = 0, 1);
rep (i, 1, suh) sub[i] += sub[i - 1];
contri(v, 0, 1), memset(sub, 0, suh + 1 << 2);
}
memset(sum, 0, mxh + 1 << 2);
for (int v: adj[u]) if (!vis[v]) {
int rt = 0;
findG(v, 0, siz[v], rt), solve(rt);
}
}
} // namespace R
int main() {
n = rint();
rep (i, 2, n) {
int u = rint(), v = rint();
adj[u].push_back(v), adj[v].push_back(u);
}
V::init(1), V::reorder(1, 1);
q = rint();
rep (i, 1, q) {
int u = rint(), v = rint(), w = V::lca(u, v); rad[i] = rint();
V::hang(u, 1, i), V::hang(v, 1, i), V::hang(w, -2, i);
R::qry[w].push_back(i);
}
int rt = 0; R::findG(1, 0, n, rt), R::solve(rt);
// rep (i, 1, q) wint(ans[i]), putchar("\n "[i < q]);
rep (u, 1, n) if (u == V::top[u]) V::solve(u);
rep (i, 1, q) wint(ans[i]), putchar('\n');
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 20ms
memory: 20344kb
input:
4988 1 2 1 3 1 4 4 5 1 6 3 7 3 8 5 9 4 10 6 11 3 12 9 13 11 14 8 15 11 16 1 17 7 18 8 19 18 20 7 21 10 22 15 23 18 24 4 25 24 26 9 27 23 28 3 29 3 30 30 31 11 32 18 33 2 34 32 35 29 36 29 37 19 38 9 39 6 40 25 41 16 42 31 43 6 44 42 45 32 46 27 47 32 48 44 49 7 50 10 51 24 52 46 53 30 54 46 55 39 56...
output:
2951 1522 4988 109 133 3728 3656 1579 4974 2039 135 288 4675 135 4954 4988 4974 1511 4981 1 1504 4825 4974 4974 1 27 4960 4669 109 4870 353 3660 693 1554 120 3079 845 201 29 4822 3006 23 29 4325 4960 409 4835 4974 32 308 24 96 115 1650 4981 3879 27 2933 119 24 4864 320 4958 158 4629 2257 1 4958 22 4...
result:
wrong answer 1st numbers differ - expected: '3226', found: '2951'
Subtask #2:
score: 0
Runtime Error
Test #9:
score: 0
Runtime Error
input:
199995 1 2 2 3 2 4 1 5 3 6 5 7 6 8 4 9 2 10 5 11 5 12 1 13 1 14 1 15 13 16 1 17 10 18 16 19 11 20 8 21 17 22 4 23 19 24 7 25 22 26 8 27 14 28 1 29 9 30 3 31 3 32 21 33 19 34 26 35 34 36 5 37 29 38 22 39 5 40 13 41 28 42 8 43 35 44 22 45 14 46 12 47 32 48 11 49 8 50 18 51 23 52 18 53 4 54 6 55 10 56 ...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Runtime Error
Test #25:
score: 0
Runtime Error
input:
199991 1 2 2 3 3 4 3 5 5 6 3 7 1 8 8 9 8 10 10 11 1 12 1 13 13 14 4 15 12 16 13 17 17 18 8 19 3 20 9 21 16 22 10 23 1 24 7 25 6 26 12 27 4 28 21 29 27 30 30 31 21 32 19 33 20 34 17 35 7 36 13 37 24 38 37 39 30 40 31 41 15 42 9 43 32 44 41 45 18 46 38 47 8 48 35 49 13 50 35 51 47 52 35 53 48 54 44 55...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%