#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pli pair<ll, ll>
#define ppi pair<pii, pii>
#define RUN_LIKE_DJAWAD (ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0));
#define DECIMAL_OUTPUT cout << fixed << setprecision(9);
#define pb push_back
#define pf push_top
#define ff first
#define ss second
#define maxn 200001
#define sq 1200
bool ac[maxn], seen[maxn], fac[maxn];
int gr[maxn], cnt[maxn], ans[maxn], ag[maxn];
vector<int> go[maxn], gv[maxn];
pii e[maxn];
int n, m, q, pt, ei, gpt;
vector<int> now;
vector<int> adj[maxn];
void dfs(int v){
seen[v] = true;
gv[gpt].pb(v);
gr[v] = gpt;
ag[gpt] = ans[v];
for (int u: adj[v]) if (not seen[u]) dfs(u);
}
vector<pii> g[maxn];
int vs;
void mdfs(int v){
seen[v] = true;
ag[v] = vs;
for (auto [u, ind]: g[v]) if (not seen[u] and ac[ind]) mdfs(u);
seen[v] = false;
}
void JL(){
if (now.empty()) return;
for (int i = 1; i < n; i++) fac[i] = ac[i];
for (int i: now) fac[i] = false;
for (int i = 1; i < n; i++) if (fac[i]){
adj[e[i].ff].pb(e[i].ss);
adj[e[i].ss].pb(e[i].ff);
}
gpt = 0;
for (int i: now){
if (not seen[e[i].ff]){
dfs(e[i].ff);
gpt++;
}
if (not seen[e[i].ss]){
dfs(e[i].ss);
gpt++;
}
}
for (int i = 1; i <= n; i++) seen[i] = false;
for (int i: now){
g[gr[e[i].ff]].pb({gr[e[i].ss], i});
g[gr[e[i].ss]].pb({gr[e[i].ff], i});
}
for (int i: now){
if (ac[i]){
cnt[i] = ag[gr[e[i].ff]];
ac[i] = false;
} else {
ac[i] = true;
vs = ag[gr[e[i].ff]] + ag[gr[e[i].ss]] - cnt[i];
mdfs(gr[e[i].ff]);
}
}
for (int i = 0; i < gpt; i++) for (int u: gv[i]) ans[u] = ag[i];
for (int i = 1; i <= n; i++) adj[i].clear();
for (int i = 0; i < gpt; i++) g[i].clear(), gv[i].clear();
}
int qi;
int main(){
RUN_LIKE_DJAWAD
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) ans[i] = 1;
for (int i = 1; i < n; i++) cin >> e[i].ff >> e[i].ss;
for (int i = 1; i <= m; i++){
cin >> ei;
go[pt].pb(ei);
if (i % sq == 0) pt++;
}
for (int i = 0; i < maxn; i++){
now = go[i];
JL();
}
while (q--){
cin >> qi;
cout << ans[qi] << "\n";
}
}
| # | 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... |