#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fi first
#define se second
const int mxN=1e5, mxM=2e5;
int n, m, q, x[mxN-1], y[mxN-1], lb[mxN-1], ans[mxN], centP[mxN], sz[mxN], rt1, sts=1, sti[mxN], mlt[mxN];
vector<pii> av[mxN-1];
vector<int> adj[mxN], cn;
struct node {
bool lz1;
int lz2, v, lc, rc;
} st[2*18*(2*mxN+mxM/2)+1]; //2 nodes per layer * logn=18 layers * total updates
inline void psh(int &sti, int v=0, bool x1=0, int x2=0) {
int lsti=sti;
if(!sti||st[sti].v!=v) {
sti=sts++;
st[sti].v=v;
if(lsti) {
st[sti].lc=st[lsti].lc, st[sti].rc=st[lsti].rc;
st[sti].lz1=st[lsti].lz1, st[sti].lz2=st[lsti].lz2;
}
}
if(x1)
st[sti].lz1=1, st[sti].lz2=0;
st[sti].lz2+=x2;
}
void upd(int sti, int l1, int r1, int x, int v=0, int l2=0, int r2=m) {
// cout << "upd " << sti << " " << l1 << " " << r1 << " " << x << " " << v << " " << l2 << " " << r2 << endl;
if(l1>r1)
return;
if(l1<=l2&&r2<=r1) {
st[sti].lz1=1, st[sti].lz2=x;
return;
}
psh(st[sti].lc, v, st[sti].lz1, st[sti].lz2);
psh(st[sti].rc, v, st[sti].lz1, st[sti].lz2);
st[sti].lz1=st[sti].lz2=0;
int m2=(l2+r2)/2;
if(l1<=m2)
upd(st[sti].lc, l1, r1, x, v, l2, m2);
if(m2<r1)
upd(st[sti].rc, l1, r1, x, v, m2+1, r2);
}
int qry(int sti, int l1, int l2=0, int r2=m) {
// cout << "qry " << sti << " " << l1 << " " << l2 << " " << r2 << endl;
if(!sti)
return 0;
if(st[sti].lz1)
return st[sti].lz2;
int m2=(l2+r2)/2;
return st[sti].lz2+(l1<=m2?qry(st[sti].lc, l1, l2, m2):qry(st[sti].rc, l1, m2+1, r2));
}
void mrg(int &sti1, int sti2) {
if(!sti1||!sti2) {
sti1^=sti2;
return;
}
st[sti1].lz2+=st[sti2].lz2;
if(st[sti2].lz1)
return;
if(st[sti1].lz1) {
st[sti1].lz1=0;
st[sti1].lc=st[sti2].lc, st[sti1].rc=st[sti2].rc;
return;
}
mrg(st[sti1].lc, st[sti2].lc);
mrg(st[sti1].rc, st[sti2].rc);
}
inline void clst() {
while(sts>1)
st[--sts]={};
for(int cni : cn)
sti[cni]=0;
}
void pst(int u, int d=-1) {
if(d==-1) {
cout << "pst " << u << endl;
u=sti[u], d=0;
}
if(!u)
return;
for(int i=0; i<d; ++i)
cout << ' ';
cout << "sti " << u << " lz " << st[u].lz1 << " " << st[u].lz2 << " v " << st[u].v << " c " << st[u].lc << " " << st[u].rc << endl;
pst(st[u].lc, d+1);
pst(st[u].rc, d+1);
}
void dfs1(int u, int p) {
sz[u]=1;
for(int e : adj[u]) {
int v=u^x[e]^y[e];
if(v==p||centP[v]!=-1)
continue;
dfs1(v, u);
sz[u]+=sz[v];
}
}
int dfs2(int u, int p, int szr) {
for(int e : adj[u]) {
int v=u^x[e]^y[e];
if(v!=p&¢P[v]==-1&&sz[v]>szr/2)
return dfs2(v, u, szr);
}
return u;
}
void dfs3(int u, int p) {
// cout << "d3 " << u << " " << p << endl;
cn.push_back(u);
mlt[u]=qry(sti[u], m);
// cout << "d32" << endl;
for(int e : adj[u]) {
int v=u^x[e]^y[e];
// cout << "d33 " << v << endl;
if(v==p||centP[v]!=-1)
continue;
sti[v]=sti[u];
psh(sti[v], v);
// cout << "d34" << endl;
for(int i=0; i<av[e].size()-1; ++i)
/*cout << "d35 " << i << endl, */upd(sti[v], av[e][i].se+1, av[e][i+1].fi-1, qry(sti[v], av[e][i].se), v);
dfs3(v, u);
// cout << "d36" << endl;
}
}
void dfs5(int u, int p) {
// cout << "d5 " << u << endl;
ans[u]-=qry(sti[rt1], mlt[u]);
for(int e : adj[u]) {
int v=u^x[e]^y[e];
if(v!=p&¢P[v]==-1)
dfs5(v, u);
}
}
void dfs4(int u, int p, int fav) {
// cout << "d4 " << u << endl;
psh(sti[u]);
upd(sti[u], fav, m, 1);
// cout << "d42" << endl;
for(int e : adj[u]) {
int v=u^x[e]^y[e];
if(v==p||centP[v]!=-1)
continue;
// cout << "d43 " << v << endl;
dfs4(v, u, av[e][1].fi);
// cout << "d44 " << endl;
for(int i=0; i<av[e].size()-1; ++i)
upd(sti[v], av[e][i].se+1, av[e][i+1].fi-1, qry(sti[v], av[e][i].se));
if(p==-1) {
rt1=v;
dfs5(v, u);
}
// pst(v), pst(u);
mrg(sti[u], sti[v]);
// cout << "d47" << endl;
}
}
void cd(int u, int p) {
// cout << "cd " << u << " " << p << endl;
int c=dfs2(u, -1, sz[u]);
// cout << "hi1" << endl;
centP[c]=p;
dfs1(c, -1);
// cout << "hi2" << endl;
psh(sti[c], c);
for(int i=0; i<=m; ++i)
upd(sti[c], i, i, i, c);
// cout << "hi3" << endl;
dfs3(c, -1);
// cout << "hi4" << endl;
clst();
dfs4(c, -1, 1);
// cout << "hi5" << endl;
// pst(c);
for(int cni : cn)
ans[cni]+=qry(sti[c], mlt[cni]);//, cout << cni << " mlt " << mlt[cni] << " sti " << sti[cni] << " ans " << ans[cni] << endl;
ans[c]+=!mlt[c];
clst();
// cout << "hi6" << endl;
cn.clear();
for(int e : adj[c]) {
int v=c^x[e]^y[e];
if(centP[v]==-1)
cd(v, c);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
for(int i=0; i<n-1; ++i) {
cin >> x[i] >> y[i], --x[i], --y[i];
adj[x[i]].push_back(i);
adj[y[i]].push_back(i);
av[i].push_back({0, 0});
}
for(int i=1; i<=m; ++i) {
int dj;
cin >> dj, --dj;
if(lb[dj]) {
av[dj].push_back({lb[dj], i-1});
lb[dj]=0;
} else
lb[dj]=i;
}
for(int i=0; i<n-1; ++i)
av[i].push_back({lb[i]?lb[i]:m+1, m+1});
// for(int i=0; i<n-1; ++i) {
// cout << "e " << x[i] << " " << y[i] << endl;
// for(pii p : av[i])
// cout << p.fi << " " << p.se << endl;
// }
memset(centP, -1, 4*n);
dfs1(0, -1);
cd(0, -2);
while(q--) {
int ck;
cin >> ck, --ck;
cout << ans[ck] << "\n";
}
}
Compilation message
synchronization.cpp: In function 'void upd(int, int, int, int, int, int, int)':
synchronization.cpp:43:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
st[sti].lz1=st[sti].lz2=0;
~~~~~~~~~~~^~
synchronization.cpp: In function 'void dfs3(int, int)':
synchronization.cpp:132:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<av[e].size()-1; ++i)
~^~~~~~~~~~~~~~~
synchronization.cpp: In function 'void dfs4(int, int, int)':
synchronization.cpp:161:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<av[e].size()-1; ++i)
~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5116 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5116 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5172 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5252 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5256 KB |
Output is correct |
| 6 |
Correct |
340 ms |
6524 KB |
Output is correct |
| 7 |
Execution timed out |
8084 ms |
22076 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8074 ms |
161552 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
161552 KB |
Output is correct |
| 2 |
Correct |
5 ms |
161552 KB |
Output is correct |
| 3 |
Correct |
9 ms |
161552 KB |
Output is correct |
| 4 |
Correct |
9 ms |
161552 KB |
Output is correct |
| 5 |
Correct |
8 ms |
161552 KB |
Output is correct |
| 6 |
Correct |
329 ms |
161552 KB |
Output is correct |
| 7 |
Execution timed out |
8083 ms |
161552 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8048 ms |
217780 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
217780 KB |
Output is correct |
| 2 |
Correct |
5 ms |
217780 KB |
Output is correct |
| 3 |
Correct |
6 ms |
217780 KB |
Output is correct |
| 4 |
Correct |
10 ms |
217780 KB |
Output is correct |
| 5 |
Correct |
344 ms |
217780 KB |
Output is correct |
| 6 |
Execution timed out |
8090 ms |
217780 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
