QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#244427 | #4941. Tree Beauty | rgnerdplayer# | WA | 46ms | 40916kb | C++20 | 2.7kb | 2023-11-09 02:24:55 | 2023-11-09 02:24:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
template <typename T>
struct Fenwick {
int n;
vector<T> a;
Fenwick(int n = 0) : n(n), a(n) {}
void add(int p, T v) {
while (p < n) {
a[p] += v;
p |= p + 1;
}
}
T sum(int p) {
T res = {};
while (p >= 0) {
res += a[p];
p = (p & p + 1) - 1;
}
return res;
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
auto solve = [&]() {
int n, q;
cin >> n >> q;
vector<vector<int>> adj(n);
for (int i = 1; i < n; i++) {
int p;
cin >> p;
adj[--p].push_back(i);
}
constexpr int K = 20;
vector<int> dep(n), par(n, -1), tin(n), tout(n), sz(n, 1);
vector childCnt(n, vector<int>(K));
int T = 0;
auto dfs = [&](auto dfs, int u) -> void {
tin[u] = T++;
childCnt[u][0]++;
for (auto v : adj[u]) {
dep[v] = dep[u] + 1;
par[v] = u;
dfs(dfs, v);
sz[u] += sz[v];
for (int i = 1; i < K; i++) {
childCnt[u][i] += childCnt[v][i - 1];
}
}
tout[u] = T;
};
dfs(dfs, 0);
Fenwick<i64> f(n), g(n);
vector childAdd(n, vector<i64>(K));
while (q--) {
int op;
cin >> op;
if (op == 1) {
int x, y, k;
cin >> x >> y >> k;
x--;
if (k == 1) {
f.add(tin[x], y);
f.add(tin[x], -y);
g.add(tin[x], 1LL * sz[x] * y);
} else {
i64 s = 0;
for (int i = 0; i < K; i++) {
childAdd[x][i] += y;
s += 1LL * childCnt[x][i] * y;
y /= k;
}
g.add(tin[x], s);
}
} else {
int x;
cin >> x;
x--;
i64 ans = f.sum(tin[x]) * sz[x] + g.sum(tout[x] - 1) - g.sum(tin[x]);
int u = x;
for (int i = 0; i < K && u != -1; i++) {
for (int j = 0; i + j < K; j++) {
ans += childAdd[u][i + j] * childCnt[x][j];
}
u = par[u];
}
cout << ans << '\n';
}
}
};
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3524kb
input:
5 5 1 1 3 3 1 1 99 2 2 1 2 3 1 3 2 3 2 3
output:
245 97 99
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 46ms
memory: 40916kb
input:
100000 100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
1818724600 1818724600 1818724600 0 2920352548 904 2920352548 1101627948 2920352548 2920352548 4492303477 5061484915 555127744 526252800 5061750398 11569471874 5034373536 5034373536 5034373536 2072854996 4981808979 26872020588 13921067785 10829155036 12550680652 25699267461 0 9006876736 12502182908 8...
result:
wrong answer 4th lines differ - expected: '672469600', found: '0'