// In the name of God
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 5e6 + 5;
int n, m, q;
vector<int> qr[N];
vector<pair<int, int> > adj[N];
bool mark[N];
int sz[N], ans[N];
vector<int> ver, E;
int inx[N];
void dfs_sz(int v, int p = 0) {
/*vector<pair<int, int> > stck;
stck.pb(mp(v, 0));
while (!stck.empty()) {
int v = stck.back().fi, p = stck.back().se;
if (sz[v] == 0) sz[v] = 1;
bool ok = true;
while (inx[v] < (int)adj[v].size()) {
int u = adj[v][inx[v]].fi, i = adj[v][inx[v]].se;
inx[v]++;
if (u == p || mark[u]) continue;
for (auto x : qr[i])
E.pb(x);
stck.pb(mp(u, v));
ok = false;
break;
}
if (ok && inx[v] == (int)adj[v].size()) {
sz[p] += sz[v];
stck.pop_back();
inx[v] = 0;
}
}
return;*/
sz[v] = 1;
for (auto [u, i] : adj[v]) {
if (!mark[u] && u != p) {
for (auto x : qr[i])
E.pb(x);
dfs_sz(u, v);
sz[v] += sz[u];
}
}
}
int find_centroid(int v, int S, int p = 0) {
for (auto [u, i] : adj[v]) {
if (!mark[u] && u != p && sz[u] * 2 > S) {
return find_centroid(u, S, v);
}
}
return v;
}
int get(int val) {
return lower_bound(E.begin(), E.end(), val) - E.begin();
}
vector<int> vec[N];
int T;
pair<int*, int> st[N << 4];
int stsz;
int inf = 1e9;
void rem(int S) {
while (stsz > S) {
*st[stsz-1].fi = st[stsz-1].se;
stsz--;
}
}
void SET(int& x, int y) {
if (y > inf) return;
st[stsz++] = mp(&x, x);
x = y;
}
int lz[N << 2], seg[N << 2];
void shift(int v, int tl, int tr) {
if (lz[v] == -1) return;
if (lz[v]==0 || tl == tr)
SET(seg[v], lz[v] * (tr - tl + 1));
if (tl < tr) {
SET(lz[v<<1], lz[v]);
SET(lz[v << 1 | 1], lz[v]);
}
SET(lz[v], -1);
}
void set_val(int l, int r, int val, int v = 1, int tl = 0, int tr = E.size()) {
if (l > r) return;
shift(v, tl, tr);
if (tl > r || tr < l) return;
if (tl >= l && tr <= r) {
SET(lz[v], val);
shift(v, tl, tr);
return;
}
int mid = (tl + tr) >> 1;
set_val(l, r, val, v << 1, tl, mid);
set_val(l, r, val, v << 1 | 1, mid + 1, tr);
SET(seg[v], seg[v << 1] + seg[v << 1 | 1]);
}
int query(int l, int r, int v = 1, int tl = 0, int tr = E.size()) {
if (l > r) return 0;
shift(v, tl, tr);
if (tl > r || tr < l) return 0;
if (tl >= l && tr <= r) {
return seg[v];
}
int mid = (tl + tr) >> 1;
return query(l, r, v << 1, tl, mid) + query(l, r, v << 1 | 1, mid + 1, tr);
}
void dfs2(int v, int i, int p = 0) {
int S = stsz;
int prv = -1;
for (int j = 0; j < (int)qr[i].size(); j += 2) {
int x = get(qr[i][j]);
set_val(get(prv + 1), x - 1, query(x, x));
prv = qr[i][j + 1];
}
set_val(get(prv + 1), get(m + 1), inf);
vec[T].pb(query(0, 0));
for (auto [u, j] : adj[v]) {
if (mark[u] || u == p) continue;
dfs2(u, j, v);
}
rem(S);
}
void dfs3(int v, int i, int p = 0) {
int S = stsz;
int prv = -1;
for (int j = 0; j < (int)qr[i].size(); j += 2) {
int x = get(qr[i][j]);
int y = query(get(prv + 1), x - 1) + query(x, x);
set_val(get(prv + 1), x - 1, 0);
set_val(x, x, y);
prv = qr[i][j + 1];
}
set_val(get(prv + 1), get(m + 1), 0);
ans[v] += query(0, get(m + 1));
for (auto [u, j] : adj[v]) {
if (mark[u] || u == p) continue;
dfs3(u, j, v);
}
rem(S);
}
void dfs(int v) {
rem(0);
ver.clear();
E.clear();
E.pb(0);
E.pb(m + 1);
E.pb(m + 2);
dfs_sz(v);
int rt = find_centroid(v, sz[v]);
mark[rt] = 1;
sort(E.begin(), E.end());
E.resize(unique(E.begin(), E.end()) - E.begin());
int k = E.size();
for (int i = 0; i < k; i++)
set_val(i, i, i);
int S = stsz;
for (auto [u, i] : adj[rt]) {
if (mark[u]) continue;
rem(S);
T = u;
vec[T].clear();
dfs2(u, i);
}
rem(0);
set_val(0, 0, 1);
for (auto [u, i] : adj[rt]) {
if (mark[u]) continue;
for (auto x : vec[u]) {
if (x < inf)
set_val(x, x, query(x, x) + 1);
}
}
ans[rt] += query(0, m + 2);
for (auto [u, i] : adj[rt]) {
if (mark[u]) continue;
S = stsz;
for (auto x : vec[u])
if (x < inf)
set_val(x, x, query(x, x) - 1);
dfs3(u, i);
rem(S);
}
for (auto [u, i] : adj[rt]) {
if (!mark[u]) dfs(u);
}
}
void solve() {
cin >> n >> m >> q;
for (int i = 1; i <= n - 1; i++) {
int v, u; cin >> v >> u;
adj[v].pb(mp(u, i)), adj[u].pb(mp(v, i));
}
for (int i = 1; i <= m; i++) {
int k; cin >> k;
qr[k].pb(i);
}
for (int i = 1; i < n; i++) {
if ((int)qr[i].size() % 2)
qr[i].pb(m + 1);
}
memset(lz, -1, sizeof lz);
dfs(1);
while (q--) {
int c; cin >> c;
cout << ans[c] << '\n';
}
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//freopen("input.in", "r", stdin);
int tc = 1; // cin >> tc;
while (tc--) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
87 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
55 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
