Time Exceeded
Code
#include <bits/stdc++.h>
using namespace std;
// #include "debug.h"
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v), g[v].push_back(u);
}
vector<vector<int>> sub(n);
vector<int> sz(n, 1);
auto merge = [&](vector<int> &u, vector<int> &v) {
if (v.size() > u.size()) {
u.swap(v);
}
for (int i : v) {
u.push_back(i);
}
};
vector<int> ans(n);
auto go = [&](auto &&go, int u, int v) -> void {
sub[u].push_back(a[u]);
for (int c : g[u]) {
if (c == v) {
continue;
}
go(go, c, u);
sz[u] += sz[c];
merge(sub[u], sub[c]);
}
vector<int> cnt(sz[u] + 1);
for (int i : sub[u]) {
if (i <= sz[u]) {
cnt[i] = 1;
}
}
for (int i = 1; i <= sz[u]; ++i) {
ans[u] += (cnt[i] == 0);
}
};
go(go, 0, 0);
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int x;
cin >> x;
cout << ans[x - 1] << '\n';
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int tc = 1;
cin >> tc;
while (tc--) {
solve();
}
}
Information
- Submit By
- Type
- Submission
- Problem
- P1157 Roy and Tree Permutation
- Contest
- Happy New Year 2025
- Language
- C++17 (G++ 13.2.0)
- Submit At
- 2025-01-02 16:08:55
- Judged At
- 2025-01-02 16:08:55
- Judged By
- Score
- 50
- Total Time
- ≥2100ms
- Peak Memory
- ≥24.891 MiB