// in the name of ALLAH
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define F first
#define S second
#define lb(x) (x&(-x))
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(l, r) ((l+r)>>1)
const int N = 2e5+9;
int RT[N], LST[N], FRST[N], AH[N], SZ[N], D[N], DS[N], DSD[N], n, m, q, stk;
vector<pii> adj[N], Yals[N];
vector<int> verts;
bitset<N> B;
set<pii> ST[N];
struct node { int mn, mx, lz; } DSG[N<<3];
struct undo { int id; node nd; } STK[N<<6];
void build(int id = 1, int l = 0, int r = m+3){
if(r-l<2) { DSG[id]={l, l, -1}; return; }
int mid = MID(l, r);
build(L(id), l, mid);
build(R(id), mid, r);
DSG[id].mx = max(DSG[L(id)].mx, DSG[R(id)].mx);
DSG[id].mn = min(DSG[L(id)].mn, DSG[R(id)].mn);
DSG[id].lz=-1;
}
void shift(int id){
int d = DSG[id].lz;
if(!(~d)) return;
STK[stk++]={L(id), DSG[L(id)]};
STK[stk++]={R(id), DSG[R(id)]};
STK[stk++]={id, DSG[id]};
DSG[L(id)] = DSG[R(id)] = {d, d, d};
DSG[id].lz=-1;
}
void addsg(int ll, int rr, int id = 1, int l = 0, int r = m+3){
if(DSG[id].mn>rr) return;
if(DSG[id].mx<ll) return;
if(DSG[id].mn>=ll&&DSG[id].mx<=rr){ STK[stk++]={id, DSG[id]}; DSG[id] = {rr, rr, rr}; return; }
int mid = MID(l, r);
if(r-l<2) return;
shift(id);
addsg(ll, rr, L(id), l, mid);
addsg(ll, rr, R(id), mid, r);
STK[stk++]={id, DSG[id]};
DSG[id].mx = max(DSG[L(id)].mx, DSG[R(id)].mx);
DSG[id].mn = min(DSG[L(id)].mn, DSG[R(id)].mn);
}
int getind(int id = 1, int l = 0, int r = m+3){
if(r-l<2) { if(DSG[id].mn==m+2) return(-1); return(l); }
int mid = MID(l, r);
shift(id);
if(DSG[R(id)].mn<=m+1) return(getind(R(id), mid, r));
return(getind(L(id), l, mid));
}
void add(int ind, int d) { for(ind++;ind<N;ind+=lb(ind)) D[ind]+=d; }
int get(int ind){
int sm=0; for(ind++;ind;ind-=lb(ind)) sm+=D[ind];
return(sm);
}
int getds(int a) { return(!DS[a]?a:DS[a]=getds(DS[a])); }
pii merg(int a, int b, int d){
a=getds(a); b=getds(b);
DSD[a]=d;
if(a^b) DS[b]=a;
return(make_pair(d, a));
}
void setsz(int u, int p) { SZ[u]=1; for(pii&x:adj[u]) if(x.F^p&&!B[x.F]) { setsz(x.F, u); SZ[u]+=SZ[x.F]; } }
int getrt(int u, int p, int sz) { for(pii&x:adj[u]) if(x.F^p&&!B[x.F]&&SZ[x.F]>(sz>>1)) return(getrt(x.F, u, sz)); return(u); }
void ini(int u, int p){
verts.push_back(u);
for(pii x:adj[u]) if(x.F^p&&!B[x.F]) ini(x.F, u);
}
void vld(set<pii>&st, int l, int r){
vector<pii> v;
while(1){
auto it = st.lower_bound({l, -1});
if(it==st.end()) break;
pii x = *it; if(x.F>r) break;
v.push_back(x); st.erase(it);
}
if(v.empty()) return;
for(pii&x:v) merg(v[0].S, x.S, r);
st.insert({r, v[0].S});
}
void DFSg(int u, int p){
for(pii&x:adj[u]) if(x.F^p&&!B[x.F]){
DFSg(x.F, u);
if(Yals[x.S].empty()) { vld(ST[x.F], 0, m+2); continue; }
vld(ST[x.F], 0, Yals[x.S][0].F);
for(int i=0;i<(int)Yals[x.S].size()-1;i++) vld(ST[x.F], Yals[x.S][i].S+1, Yals[x.S][i+1].F);
vld(ST[x.F], Yals[x.S].back().S+1, m+2);
}
int arshad=0; for(pii&x:adj[u]) if(x.F^p&&!B[x.F]&&SZ[x.F]>=SZ[arshad]) arshad=x.F;
if(!arshad){
ST[u].insert({0, u});
return;
}
ST[u].swap(ST[arshad]);
ST[u].insert({0, u});
for(pii&x:adj[u]) if(x.F^p&&x.F^arshad&&!B[x.F]) for(pii y:ST[x.F]) ST[u].insert(y);
}
void emal(int u, int p, int d){
add(FRST[u], d);
for(pii&x:adj[u]) if(x.F^p&&!B[x.F]) emal(x.F, u, d);
}
void Do(int u, int p){
if(~LST[u]){
RT[u]+=get(LST[u]);
for(pii&x:adj[u]) if(x.F^p&&!B[x.F]) Do(x.F, u);
}
}
void redo(int x) { while(stk>x) { stk--; DSG[STK[stk].id]=STK[stk].nd; } }
void DFS(int u, int p){
if(LST[p]==-1){
LST[u]=-1;
for(pii&x:adj[u]) if(x.F^p&&!B[x.F]) DFS(x.F, u);
return;
}
LST[u]=getind();
if(LST[u]==-1){
for(pii&x:adj[u]) if(x.F^p&&!B[x.F]) DFS(x.F, u);
return;
}
for(pii&x:adj[u]) if(x.F^p&&!B[x.F]){
if(Yals[x.S].empty()){
int ah=stk;
addsg(0, m+2);
DFS(x.F, u);
redo(ah); continue;
}
int ah=stk;
addsg(0, Yals[x.S][0].F);
for(int i=0;i<(int)Yals[x.S].size()-1;i++) addsg(Yals[x.S][i].F+1, Yals[x.S][i+1].F);
addsg(Yals[x.S].back().S+1, m+2);
DFS(x.F, u);
redo(ah);
}
}
void darkol(int u){
setsz(u, 0);
u=getrt(u, 0, SZ[u]);
B[u]=1; for(pii&x:adj[u]) if(!B[x.F]) darkol(x.F); B[u]=0;
while(verts.size()) verts.pop_back();
ini(u, 0);
for(int&x:verts) { DS[x]=0; DSD[x]=0; LST[x]=-1; while(ST[x].size()) ST[x].erase(ST[x].begin()); }
DFSg(u, 0);
for(int&x:verts) FRST[x]=DSD[getds(x)];
DFS(u, 0);
for(int t=0;t<2;t++){
for(pii&x:adj[u]) if(!B[x.F]){
Do(x.F, u);
emal(x.F, u, 1);
}
for(pii&x:adj[u]) if(!B[x.F]) emal(x.F, u, -1);
reverse(adj[u].begin(), adj[u].end());
}
for(int&x:verts) if(x^u){
if(FRST[x]<=m) RT[u]++;
if(~LST[x]) RT[x]++;
}
}
int main(){
scanf("%d %d %d", &n, &m, &q);
for(int i=1;i<n;i++){
int a, b; scanf("%d %d", &a, &b);
adj[a].push_back({b, i});
adj[b].push_back({a, i});
}
memset(LST, -1, sizeof(LST)); for(int i=1;i<=m;i++){
int a; scanf("%d", &a);
if(~LST[a]) { Yals[a].push_back({LST[a], i}); LST[a]=-1; }
else LST[a]=i;
}
LST[0]=0;
for(int i=1;i<n;i++) if(~LST[i]) Yals[i].push_back({LST[i], m+1});
build();
darkol(1);
for(int Q=0;Q<q;Q++){
int a; scanf("%d", &a);
printf("%d\n", RT[a]+1);
}
}
Compilation message
synchronization.cpp: In function 'int main()':
synchronization.cpp:165:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &m, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:167:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:172:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a; scanf("%d", &a);
~~~~~^~~~~~~~~~
synchronization.cpp:181:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a; scanf("%d", &a);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
19968 KB |
Output is correct |
| 2 |
Correct |
23 ms |
19968 KB |
Output is correct |
| 3 |
Correct |
19 ms |
19968 KB |
Output is correct |
| 4 |
Correct |
20 ms |
19968 KB |
Output is correct |
| 5 |
Correct |
20 ms |
19968 KB |
Output is correct |
| 6 |
Correct |
26 ms |
20096 KB |
Output is correct |
| 7 |
Correct |
131 ms |
22264 KB |
Output is correct |
| 8 |
Correct |
115 ms |
22224 KB |
Output is correct |
| 9 |
Correct |
148 ms |
22400 KB |
Output is correct |
| 10 |
Correct |
1999 ms |
39968 KB |
Output is correct |
| 11 |
Correct |
1967 ms |
40008 KB |
Output is correct |
| 12 |
Correct |
1181 ms |
41856 KB |
Output is correct |
| 13 |
Correct |
449 ms |
45408 KB |
Output is correct |
| 14 |
Correct |
2588 ms |
39848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1319 ms |
72000 KB |
Output is correct |
| 2 |
Correct |
1194 ms |
71424 KB |
Output is correct |
| 3 |
Correct |
1832 ms |
78880 KB |
Output is correct |
| 4 |
Correct |
1959 ms |
79408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
19968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1354 ms |
41980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
20008 KB |
Output is correct |
| 2 |
Correct |
19 ms |
19968 KB |
Output is correct |
| 3 |
Correct |
21 ms |
19968 KB |
Output is correct |
| 4 |
Incorrect |
20 ms |
19968 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
