QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#418332#3748. 买一送一ZayinCTT#AC ✓70ms18832kbC++14738b2024-05-23 12:47:472024-05-23 12:47:49

Judging History

This is the latest submission verdict.

  • [2024-05-23 12:47:49]
  • Judged
  • Verdict: AC
  • Time: 70ms
  • Memory: 18832kb
  • [2024-05-23 12:47:47]
  • Submitted

answer

#include<iostream>
#include<vector>
using ll = long long;
int n, a[100005], c[100005], p[100005]; ll f[100005];
std::vector<int> son[100005];
void dfs(int u) {
	static int C; static ll D; c[u] = C;
	int x = p[a[u]]; D -= c[x];
	if (!x) C++; p[a[u]] = u, D += c[u];
	f[u] = D;
	for (int v : son[u]) dfs(v);
	if (!x) C--; D -= c[u], p[a[u]] = x, D += c[x];
}
int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
	while (std::cin >> n) {
		for (int i = 2; i <= n; i++) {
			int x; std::cin >> x, son[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++) son[i].clear();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 70ms
memory: 18832kb

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