QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#306898 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | YeahPotato | 0 | 11ms | 36932kb | C++14 | 5.2kb | 2024-01-17 15:31:57 | 2024-01-17 15:31:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, M = N << 1;
int n, q, u, v, k, lca, edgenum, Head[N], Next[M], vet[M], ans[N];
int fa[N], dep[N], siz[N], son[N], top[N];
int mx, tree[N], P, id[N], val[N], tag[N], tot, cg, Max[N], _mx, buc[N], exc[N], vis[N], cur, stk[N], le[N], ri[N];
struct qry { int a, b, c; } ; basic_string <qry> hpath[N], subtree[N], single[N];
int read() {
int s = 0; char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s;
}
void write(int x) {
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
void add(int u, int v) {
Next[++edgenum] = Head[u];
Head[u] = edgenum;
vet[edgenum] = v;
}
void dfs1(int u, int f) {
fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;
for (int e=Head[u]; e; e=Next[e]) {
int v=vet[e];
if (v ^ f) {
dfs1(v, u), siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
}
void dfs2(int u, int t) {
top[u] = t;
if (son[u]) dfs2(son[u], t);
for (int e=Head[u]; e; e=Next[e]) {
int v=vet[e];
if (v != fa[u] && v != son[u])
dfs2(v, v);
}
}
int getlca(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;
}
void addq(int u, int k, int i, int c) {
ans[i] += c * dep[u];
while (u) {
if (son[u] && k) subtree[son[u]] += (qry) {k - 1, i, c};
hpath[u] += (qry) {k, i, c};
if (fa[u=top[u]] && k) subtree[u] += (qry) {k - 1, i, - c};
u = fa[u];
}
}
void update(int s) {
for (; s<=n; s+=s&-s) tree[s] ++;
}
int getsum(int s) {
int res = 0;
for (; s; s-=s&-s) res += tree[s];
return res;
}
void clear(int s) {
for (; s<=n && tree[s]; s+=s&-s) tree[s] = 0;
}
void dfs3(int u, int d) {
mx = max(mx, d), update(d);
for (int e=Head[u]; e; e=Next[e])
if (vet[e] ^ fa[u])
dfs3(vet[e], d + 1);
}
void solvehpath(int u) {
int _ = u; mx = 0;
for (; u; u=son[u]) {
for (int e=Head[u]; e; e=Next[e]) {
int v=vet[e];
if (v == fa[u] || v == son[u]) continue;
dfs3(v, 1);
}
for (qry t : hpath[u])
ans[t.b] += t. c * getsum(t. a);
}
for (int i=1; i<=mx; i++) clear(i);
for (u=_; u; u=son[u])
for (int e=Head[u]; e; e=Next[e]) {
int v=vet[e];
if (v != fa[u] && v != son[u])
solvehpath(v);
}
}
void dfs4(int u) {
dep[u] = son[u] = 0;
for (int e=Head[u]; e; e=Next[e]) {
int v=vet[e];
if (v ^ fa[u]) {
dfs4(v), dep[u] = max(dep[u], dep[v] + 1);
if (dep[v] > dep[son[u]]) son[u] = v;
}
}
}
void solvesubtree(int u) {
if (! id[u]) id[u] = P + 1, P += dep[u] + 1;
if (son[u]) id[son[u]] = id[u] + 1, solvesubtree(son[u]);
tag[u] = tag[son[u]];
for (int e=Head[u]; e; e=Next[e]) {
int v=vet[e];
if (v == fa[u] || v == son[u]) continue;
solvesubtree(v), tag[u] += tag[v] + val[id[v]+dep[v]];
for (int i=0; i<=dep[v]; i++)
val[id[u]+i+1] += val[id[v]+i] - val[id[v]+dep[v]];
} val[id[u]] = 1 - tag[u];
for (qry t : subtree[u])
ans[t.b] += t. c * (val[id[u]+min(t.a,dep[u])] + tag[u]);
}
#define find(u,s) (tot = s, cg = 0, getroot(u, 0), cg)
void getroot(int u, int fa) {
siz[u] = 1;
for (int e=Head[u]; e; e=Next[e]) {
int v=vet[e];
if (v != fa && ! vis[v]) {
getroot(v, u), siz[u] += siz[v];
Max[u] = max(Max[u], siz[v]);
}
} Max[u] = max(Max[u], tot - siz[u]);
if (Max[u] < Max[cg]) cg = u;
}
void dfs5(int u, int fa, int d) {
mx = max(mx, d), stk[++cur] = d, buc[d] ++;
for (int e=Head[u]; e; e=Next[e]) {
int v=vet[e];
if (v != fa && ! vis[v])
dfs5(v, u, d + 1);
}
}
void dfs6(int u, int fa, int d) {
for (qry t : single[u])
if (t. a >= d)
ans[t.b] += t. c * (buc[min(t.a-d,mx)] - exc[min(t.a-d,_mx)]);
siz[u] = 1;
for (int e=Head[u]; e; e=Next[e]) {
int v=vet[e];
if (v != fa && ! vis[v])
dfs6(v, u, d + 1), siz[u] += siz[v];
}
}
void solvesingle(int u) {
vis[u] = 1, stk[cur=1] = 0, buc[mx=0] = 1;
for (int e=Head[u]; e; e=Next[e]) {
int v=vet[e];
if (vis[v]) continue;
le[v] = cur + 1, dfs5(v, u, 1), ri[v] = cur;
}
for (int i=1; i<=mx; i++) buc[i] += buc[i-1];
for (qry t : single[u]) ans[t.b] += t. c * buc[min(t.a,mx)];
for (int e=Head[u]; e; e=Next[e]) {
int v=vet[e];
if (vis[v]) continue;
_mx = 0;
for (int i=le[v]; i<=ri[v]; i++) _mx = max(_mx, stk[i]), exc[stk[i]] ++;
for (int i=1; i<=_mx; i++) exc[i] += exc[i-1];
dfs6(v, u, 1);
for (int i=1; i<=_mx; i++) exc[i] = 0;
}
for (int i=0; i<=mx; i++) buc[i] = 0;
for (int e=Head[u]; e; e=Next[e]) {
int v=vet[e];
if (! vis[v]) solvesingle(find(v, siz[v]));
}
}
int main() {
n = read();
for (int i=1; i<n; i++)
u = read(), v = read(), add(u, v), add(v, u);
dfs1(1, 0), dfs2(1, 1);
q = read();
for (int i=1; i<=q; i++) {
u = read(), v = read(), k = read(), lca = getlca(u, v);
if (v == lca) swap(u, v);
if (u ^ v)
if (u ^ lca) addq(u, k, i, 1), addq(v, k, i, 1), addq(lca, k, i, - 2);
else addq(v, k, i, 1), addq(u, k, i, - 1);
single[lca] += (qry) {k, i, 1};
}
solvehpath(1);
dfs4(1), solvesubtree(1);
Max[0] = 1e9, solvesingle(find(1, n));
for (int i=1; i<=q; i++)
write(ans[i]), putchar('\n');
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 11ms
memory: 36932kb
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:
3512 2199 6586 209 254 4586 4406 2164 6399 2188 308 393 5830 314 5439 5598 6232 1546 6149 12 1920 5324 6392 5370 19 82 6539 5392 209 5430 472 3998 809 1944 214 3902 1231 272 84 5174 3730 70 81 5225 6389 674 5903 6187 113 496 75 164 210 2282 6294 4929 100 3426 234 66 5126 535 6064 392 5371 2481 15 55...
result:
wrong answer 1st numbers differ - expected: '3226', found: '3512'
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%