QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#915564 | #3748. 买一送一 | Horcruxs# | AC ✓ | 71ms | 18688kb | C++26 | 1.1kb | 2025-02-26 13:00:40 | 2025-02-26 13:00:41 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
int n;
std::vector <int> a(100005), c(100005), p(100005);
std::vector <i64> f(100005);
std::vector <int> s[100005];
void dfs(int u) {
static int C;
static i64 D;
c[u] = C;
int x = p[a[u]];
D -= c[x];
if(x == 0) {
C++;
}
p[a[u]] = u;
D += c[u];
f[u] = D;
for(int v : s[u]) {
dfs(v);
}
if(x == 0) {
C--;
}
D -= c[u];
p[a[u]] = x;
D += c[x];
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
while(std::cin >> n) {
for(int i = 2; i <= n; i++) {
int x;
std::cin >> x;
s[x].push_back(i);
}
for(int i = 1; i <= n; i++) {
std::cin >> a[i];
}
dfs(1);
for(int i = 2; i <= n; i++) {
std::cout << f[i] << '\n';
}
for(int i = 1; i <= n; i++) {
s[i].clear();
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 71ms
memory: 18688kb
input:
100 1 2 3 4 5 5 7 7 9 10 11 12 13 13 15 13 12 18 12 11 10 7 7 4 25 26 27 4 2 30 31 32 33 34 34 36 34 33 33 33 32 32 30 2 45 1 47 48 49 50 51 52 53 52 55 56 56 52 59 60 59 59 63 64 51 66 49 68 69 68 47 72 73 72 75 76 77 78 79 80 80 82 77 84 77 86 76 88 75 72 91 92 72 94 94 96 97 94 72 55 12 85 53 40 ...
output:
1 3 6 10 15 15 21 21 28 30 38 47 57 57 68 55 47 57 47 38 36 21 21 10 15 21 28 10 3 6 10 15 21 28 28 36 28 21 21 21 15 15 6 3 6 1 3 6 10 15 21 28 36 28 36 45 45 28 36 45 30 36 45 55 21 28 10 15 17 15 3 6 10 6 10 15 21 28 36 45 45 55 21 28 21 28 15 21 10 6 10 15 6 10 10 15 21 10 6 1 3 6 6 10 15 21 28 ...
result:
ok 498996 numbers