QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#88832 | #5372. 杀蚂蚁简单版 | Scintilla | 0 | 97ms | 25836kb | C++14 | 2.6kb | 2023-03-17 17:37:01 | 2023-03-17 17:37:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl
const int P = 998244353;
const int N = 1e5 + 10;
int read() {
int x = 0, f = 1; char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
return x * f;
}
int inc(int a, int b) { return (a += b) >= P ? a - P : a; }
int dec(int a, int b) { return (a -= b) < 0 ? a + P : a; }
int mul(int a, int b) { return 1ll * a * b % P; }
int qpow(int a, int b) { int res = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a); return res; }
int n, a[N], k[N], b[N], x[N], dfn[N], dn, p[N], dep[N], st[N][20];
vector <int> e[N];
void dfs0(int u, int fa) {
dfn[u] = ++ dn, st[dfn[u]][0] = u, p[u] = fa;
if (u == 2) k[u] = 1, b[u] = 0;
else if (u > 2) {
int q = mul(a[p[p[u]]], qpow(a[p[p[u]]] + a[u], P - 2)), iv = qpow(dec(1, q), P - 2);
k[u] = mul(dec(k[p[u]], mul(q, k[p[p[u]]])), iv);
b[u] = mul(dec(dec(b[p[u]], mul(q, b[p[p[u]]])), 1), iv);
}
x[u] = mul(dec(dec(b[u], b[p[u]]), 1), qpow(dec(k[p[u]], k[u]), P - 2));
for (int v : e[u]) if (v != fa) {
dep[v] = dep[u] + 1, dfs0(v, u);
}
// cout << "u, k[u], b[u], x[u] = " << u << ' ' << k[u] << ' ' << b[u] << ' ' << x[u] << endl;
}
int Min(int u, int v) {
return dep[u] < dep[v] ? u : v;
}
int LCA(int u, int v) {
if (u == v) return u;
u = dfn[u], v = dfn[v];
if (u > v) swap(u, v);
int t = __lg(v - u);
return p[Min(st[u + 1][t], st[v - (1 << t) + 1][t])];
}
int main() {
n = read();
rep(i, 1, n) a[i] = read();
rep(i, 1, n - 1) {
int u = read(), v = read();
e[u].pb(v), e[v].pb(u);
}
dfs0(1, 0);
rep(j, 1, 19) rep(i, 1, n - (1 << j) + 1) {
st[i][j] = Min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
for (int q = read(); q; -- q) {
auto ask = [&](int u, int v) {
if (u == 1) return 0;
int lca = LCA(u, v);
// cout << "u, v, lca = " << u << ' ' << v << ' ' << lca << endl;
return inc(mul(k[lca], x[u]), b[lca]);
} ;
int s = read(), u = read(), v = read(), lca = LCA(u, v), res = 0;
res = inc(res, inc(ask(u, s), ask(v, s)));
res = dec(res, inc(ask(lca, s), ask(p[lca], s)));
printf("%d\n", res);
}
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: 4ms
memory: 5860kb
input:
5 1 1 1 1 1 1 2 2 3 2 4 3 5 1 2 4 2
output:
3
result:
wrong answer 1st lines differ - expected: '4', found: '3'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #18:
score: 0
Wrong Answer
time: 97ms
memory: 25836kb
input:
100000 13643 13546 7538 2233 7731 14619 19601 8438 9556 19888 17313 1060 15168 11207 11183 16074 10758 7469 13444 9658 18326 4735 7542 13836 5863 7903 7212 14714 10416 18506 13435 14502 15271 13205 14887 18074 8353 19807 1767 19148 7343 10823 14211 66 17168 8305 1210 5436 18552 3659 886 18416 19261 ...
output:
945511877 445444586 463961236 617195216 102986704 129776727 484789584 988144777 928938142 975749437 983816511 924770936 150160212 394521836 99392055 984326661 988730298 533211997 423984827 207936943 176462435 100763154 128521063 250869128 750240601 856011657 850993259 650007918 362290111 866226530 3...
result:
wrong answer 1st lines differ - expected: '470097670', found: '945511877'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%