#include <bits/stdc++.h>
using namespace std;
// DEBUG TOOLS
#ifdef _LOCAL
#define LOG(msg) cerr << "DEBUG: " << msg << endl
#else
#define LOG(msg)
#endif
// DEBUG TOOLS
int n, m, q;
vector<vector<pair<int, int>>> g;
vector<vector<pair<int, int>>> et;
vector<int> roots;
vector<int> solve(int root) {
multiset<int> s = {0};
auto dfs = [&s](const auto& self, int u, int par, map<int, int> m_cur) -> void {
for (auto [i, v] : g[u]) {
if (v == par) continue;
LOG("BRUH KOTHAY " << i << ' ' << v);
map<int, int> m_nxt;
for (auto [l, r] : et[i]) {
LOG("HELLO " << u << ' ' << v << ' ' << l << ' ' << r);
auto itr = m_cur.lower_bound(l);
if (itr == m_cur.end()) continue;
m_nxt[r] = max(itr->second, l);
}
LOG("UMM");
if (m_nxt.empty()) continue;
s.insert(m_nxt.begin()->second);
LOG("SHESH");
self(self, v, u, m_nxt);
}
};
dfs(dfs, root, -1, {{m + 1, 0}});
vector<int> ret(s.begin(), s.end());
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> q;
if (q != 1) return 0;
g.resize(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back(make_pair(i, v));
g[v].push_back(make_pair(i, u));
}
et.resize(n - 1);
for (int i = 1; i <= m; i++) {
int j;
cin >> j;
j--;
if (et[j].empty() or et[j].back().second != m + 1) et[j].push_back(make_pair(i, m + 1));
else et[j].back().second = i;
}
roots.resize(q);
for (int &v : roots) {
cin >> v;
v--;
}
vector<int> ans = solve(roots[0]);
cout << ans.size() << endl;
// cerr << ans.size() << endl;
// for (int t : ans) {
// cerr << t << ' ';
// }
// cout << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |