#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vct vector
#define pii pair<int, int>
#define fir first
#define sec second
#define mpii make_pair
#define lb lower_bound
#define ub upper_bound
#define hmap unordered_map
const int MX_N = 1e5 + 5, INF = 1e9;
int n, m, q;
arr<vct<pii>, MX_N> adj;
arr<vct<pii>, MX_N> rngs;
arr<bool, MX_N> dltd;
arr<int, MX_N> sz;
void cmp_szs(int u, int pr = -1) {
sz[u] = 1;
for (pii x : adj[u]) {
if (dltd[x.fir] || x.fir == pr) continue;
cmp_szs(x.fir, u);
sz[u] += sz[x.fir];
}
}
int gt_cnt(int u, int whl_sz, int pr = -1) {
for (pii x : adj[u]) {
if (dltd[x.fir] || x.fir == pr) continue;
if (2 * sz[x.fir] > whl_sz) return gt_cnt(x.fir, whl_sz, u);
}
return u;
}
arr<int, MX_N> cnt_pr;
void cmp_prs(int u, int cnt, int pr = -1) {
if (u != cnt) cnt_pr[u] = cnt;
for (pii x : adj[u]) {
if (dltd[x.fir] || x.fir == pr) continue;
cmp_prs(x.fir, cnt, u);
}
}
arr<int, MX_N> dsu_pr;
arr<vct<int>, MX_N> fmly;
int gt_pr(int u) {
if (dsu_pr[u] == u) return u;
dsu_pr[u] = gt_pr(dsu_pr[u]);
return dsu_pr[u];
}
void mrg_fmly(int u, int v) {
u = gt_pr(u), v = gt_pr(v);
assert(u != v);
if (fmly[u].size() < fmly[v].size()) swap(u, v);
for (int x : fmly[v]) fmly[u].push_back(x);
dsu_pr[v] = u;
}
arr<map<int, int>, MX_N> frm_mp, twrd_mp;
void mrg_it(map<int, vct<int>>& x, auto& it1, auto& it2) {
int vl = it1->fir;
if (it1->sec.size() < it2->sec.size()) swap(it1, it2);
for (int y : it2->sec) it1->sec.push_back(y);
x.erase(it2);
it1->fir = vl;
}
void mrg_mp(map<int, int>& x, map<int, int>& y) {
if (x.size() < y.size()) x.swap(y);
for (pii z : y) {
if (x.count(z.fir)) mrg_fmly(x[z.fir], z.sec);
else x.insert(z);
}
}
void mdfy_frm(map<int, int>& x, vct<pii>& y) {
int lst = (y.size()) ? y.back().sec : -1;
while (x.size() && x.rbegin()->fir > lst) x.erase(next(x.end(), -1));
for (int i = 0; i < y.size(); i++) {
vct<int> cmb;
if (x.lb(y[i].fir) == x.begin()) continue;
for (auto it = next(x.lb(y[i].fir), -1); ; it--) {
if (i != 0 && it->fir <= y[i - 1].sec) break;
cmb.push_back(it->fir);
if (it == x.begin()) break;
}
int u = (x.count(y[i].fir)) ? x[y[i].fir] : -1;
for (int z : cmb) {
if (u == -1) u = x[z];
else mrg_fmly(u, x[z]);
x.erase(z);
}
if (u != -1) x[y[i].fir] = u;
}
}
void cmp_frms(int u, int pr = -1) {
dsu_pr[u] = u, fmly[u] = {u};
frm_mp[u] = {{1, u}};
for (pii x : adj[u]) {
if (dltd[x.fir] || x.fir == pr) continue;
cmp_frms(x.fir, u);
mdfy_frm(frm_mp[x.fir], rngs[x.sec]);
mrg_mp(frm_mp[u], frm_mp[x.fir]);
}
}
void mdfy_twrd(map<int, int>& x, vct<pii>& y) {
int frst = (y.size()) ? y[0].fir : INF;
while (x.size() && x.begin()->fir < frst) x.erase(x.begin());
for (int i = 0; i < y.size(); i++) {
vct<int> cmb;
for (auto it = x.ub(y[i].sec); it != x.end(); it++) {
if (i + 1 != y.size() && it->fir >= y[i + 1].fir) break;
cmb.push_back(it->fir);
}
int u = (x.count(y[i].sec)) ? x[y[i].sec] : -1;
for (int z : cmb) {
if (u == -1) u = x[z];
else mrg_fmly(u, x[z]);
x.erase(z);
}
if (u != -1) x[y[i].sec] = u;
}
}
void cmp_twrds(int u, int pr = -1) {
dsu_pr[u] = u, fmly[u] = {u};
twrd_mp[u] = {{m, u}};
for (pii x : adj[u]) {
if (dltd[x.fir] || x.fir == pr) continue;
cmp_twrds(x.fir, u);
mdfy_twrd(twrd_mp[x.fir], rngs[x.sec]);
mrg_mp(twrd_mp[u], twrd_mp[x.fir]);
}
}
arr<hmap<int, int>, MX_N> frm, twrd;
void bld(int u = 1) {
cmp_szs(u);
int cnt = gt_cnt(u, sz[u]);
cmp_prs(cnt, cnt);
cmp_frms(cnt);
for (pii x : frm_mp[cnt])
for (int y : fmly[gt_pr(x.sec)]) frm[cnt][y] = x.fir;
cmp_twrds(cnt);
for (pii x : twrd_mp[cnt])
for (int y : fmly[gt_pr(x.sec)]) twrd[cnt][y] = x.fir;
// cout << cnt << ": ";
// // for (pii x : frm[cnt]) cout << x.fir << "," << x.sec << " ";
// for (pii x : twrd[cnt]) cout << x.fir << "," << x.sec << " ";
// cout << endl;
dltd[cnt] = true;
for (pii x : adj[cnt])
if (!dltd[x.fir]) bld(x.fir);
}
arr<vct<int>, MX_N> chldrn;
int nm_inds;
arr<int, MX_N> ind, fn_ind, rv_ind;
void cmp_inds(int u) {
nm_inds++, ind[u] = nm_inds, rv_ind[nm_inds] = u;
for (int v : chldrn[u]) cmp_inds(v);
fn_ind[u] = nm_inds;
}
arr<vct<pair<int, pii>>, MX_N> qrys;
arr<vct<pii>, MX_N> upds;
void prcmp() {
bld();
for (int u = 1; u <= n; u++) chldrn[cnt_pr[u]].push_back(u);
for (int u = 1; u <= n; u++)
if (cnt_pr[u] == 0) { cmp_inds(u); break; }
for (int u = 1; u <= n; u++) {
for (int i = ind[u]; i <= fn_ind[u]; i++) upds[u].push_back({frm[u][rv_ind[i]], rv_ind[i]});
int lst = -1, v = u;
while (v != 0) {
qrys[v].push_back({twrd[v][u], {u, lst}});
lst = v, v = cnt_pr[v];
}
}
for (int u = 1; u <= n; u++)
sort(upds[u].begin(), upds[u].end()), sort(qrys[u].begin(), qrys[u].end());
// for (int u = 1; u <= n; u++) {
// cout << u << ": ";
// // for (pii x : upds[u]) cout << x.sec << "," << x.fir << " ";
// for (pair<int, pii> x : qrys[u]) cout << x.sec.fir << "," << x.sec.sec << "," << x.fir << " ";
// cout << endl;
// }
}
vct<int> sgtr;
void upd(int i, int x, int hg, int lw = 1, int u = 1) {
if (i < lw || hg < i) return;
if (lw == hg) { sgtr[u] += x; return; }
int md = (lw + hg) / 2;
upd(i, x, md, lw, 2 * u), upd(i, x, hg, md + 1, 2 * u + 1);
sgtr[u] = sgtr[2 * u] + sgtr[2 * u + 1];
}
int qry(int l, int r, int hg, int lw = 1, int u = 1) {
if (r < lw || hg < l) return 0;
if (l <= lw && hg <= r) return sgtr[u];
int md = (lw + hg) / 2;
return qry(l, r, md, lw, 2 * u) + qry(l, r, hg, md + 1, 2 * u + 1);
}
arr<int, MX_N> ans;
void cmp(int u) {
sgtr.clear(), sgtr.resize(4 * (fn_ind[u] - ind[u]) + 10);
int i = 0;
for (pair<int, pii> x : qrys[u]) {
while (i != upds[u].size() && upds[u][i].fir <= x.fir) {
upd(ind[upds[u][i].sec] - ind[u] + 1, 1, fn_ind[u] - ind[u] + 1);
i++;
}
ans[x.sec.fir] += qry(1, fn_ind[u] - ind[u] + 1, fn_ind[u] - ind[u] + 1);
if (x.sec.sec != -1) ans[x.sec.fir] -= qry(ind[x.sec.sec] - ind[u] + 1, fn_ind[x.sec.sec] - ind[u] + 1, fn_ind[u] - ind[u] + 1);
}
}
int main() {
// freopen("sync.in", "r", stdin);
cin >> n >> m >> q;
for (int i = 1; i <= n - 1; i++) {
int u, v; cin >> u >> v;
adj[u].push_back({v, i}), adj[v].push_back({u, i});
}
for (int i = 1; i <= m; i++) {
int j; cin >> j;
if (rngs[j].empty() || rngs[j].back().sec != 0) rngs[j].push_back({i, 0});
else rngs[j].back().sec = i - 1;
}
for (int i = 1; i <= n - 1; i++)
if (rngs[i].size() && rngs[i].back().sec == 0) rngs[i].back().sec = m;
prcmp();
for (int u = 1; u <= n; u++) cmp(u);
for (int i = 1; i <= q; i++) {
int u; cin >> u;
cout << ans[u] << endl;
}
}
Compilation message
synchronization.cpp:60:36: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
60 | void mrg_it(map<int, vct<int>>& x, auto& it1, auto& it2) {
| ^~~~
synchronization.cpp:60:47: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
60 | void mrg_it(map<int, vct<int>>& x, auto& it1, auto& it2) {
| ^~~~
synchronization.cpp: In function 'void mdfy_frm(std::map<int, int>&, std::vector<std::pair<int, int> >&)':
synchronization.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int i = 0; i < y.size(); i++) {
| ~~^~~~~~~~~~
synchronization.cpp: In function 'void mdfy_twrd(std::map<int, int>&, std::vector<std::pair<int, int> >&)':
synchronization.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for (int i = 0; i < y.size(); i++) {
| ~~^~~~~~~~~~
synchronization.cpp:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | if (i + 1 != y.size() && it->fir >= y[i + 1].fir) break;
| ~~~~~~^~~~~~~~~~~
synchronization.cpp: In function 'void cmp(int)':
synchronization.cpp:214:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
214 | while (i != upds[u].size() && upds[u][i].fir <= x.fir) {
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
34908 KB |
Output is correct |
| 2 |
Correct |
15 ms |
34904 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
34908 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
783 ms |
216776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
34920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
867 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
34908 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
34908 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
