#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
int N, M, Q;
pii E[MAXN+10];
vector<int> A[MAXN+10];
vector<pii> adj[MAXN+10];
int sz[MAXN+10], del[MAXN+10];
int par[MAXN+10], edge[MAXN+10], head[MAXN+10];
void getsz(int now, int bef)
{
sz[now]=1;
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
if(del[nxt.first]) continue;
par[nxt.first]=now;
edge[nxt.first]=nxt.second;
getsz(nxt.first, now);
sz[now]+=sz[nxt.first];
}
}
int getcen(int now, int bef, int S)
{
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
if(del[nxt.first]) continue;
if(sz[nxt.first]>S/2) return getcen(nxt.first, now, S);
}
return now;
}
int idx[MAXN+10], invidx[MAXN+10], cnt;
struct UF
{
int par[MAXN+10];
int Find(int x) { return x==par[x] ? x : par[x]=Find(par[x]); }
int Union(int x, int y)
{
x=Find(x); y=Find(y);
if(x==y) return x;
par[x]=y;
return y;
}
}uf;
set<int> S[MAXN+10];
vector<int> V;
void hld(int now, int bef)
{
//printf("!%d\n", now);
V.push_back(now);
idx[now]=++cnt;
invidx[idx[now]]=now;
int heavy=0;
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
if(del[nxt.first]) continue;
if(sz[heavy]<sz[nxt.first]) heavy=nxt.first;
}
if(heavy==0) return;
head[heavy]=head[now];
hld(heavy, now);
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
if(del[nxt.first]) continue;
if(nxt.first==heavy) continue;
head[nxt.first]=nxt.first;
hld(nxt.first, now);
}
}
int col[MAXN+10], val[MAXN+10], ts[MAXN+10], te[MAXN+10];
int ans[MAXN+10];
void fs(int now)
{
for(auto it : V)
{
uf.par[it]=it;
col[it]=1;
val[it]=it;
S[it].clear();
ts[it]=M+1;
}
for(auto it : V) S[head[it]].insert(idx[it]);
vector<pii> VT;
for(auto it : V) if(it!=now) for(auto jt : A[edge[it]]) VT.push_back({jt, it});
sort(VT.begin(), VT.end());
for(auto it : VT)
{
int v=it.second, t=it.first;
if(col[v])
{
S[head[v]].erase(idx[v]);
if(val[v])
{
int u=v;
while(1)
{
auto pt=S[head[u]].upper_bound(idx[u]);
if(pt==S[head[u]].begin()) u=par[head[u]];
else { u=invidx[*(--pt)]; break; }
}
if(u==now)
{
if(val[v]) ts[val[v]]=t;
}
else
{
if(val[u]==0) val[u]=val[v];
else val[u]=uf.Union(val[u], val[v]);
}
val[v]=0;
}
col[v]=0;
}
else
{
S[head[v]].insert(idx[v]);
col[v]=1;
}
}
for(auto it : V) if(it!=now) ts[it]=ts[uf.Find(it)];
}
void fe(int now)
{
for(auto it : V)
{
uf.par[it]=it;
col[it]=1;
val[it]=it;
S[it].clear();
te[it]=0;
}
for(auto it : V) S[head[it]].insert(idx[it]);
vector<pii> VT;
for(auto it : V) if(it!=now) for(auto jt : A[edge[it]]) VT.push_back({jt, it});
sort(VT.begin(), VT.end(), greater<pii>());
for(auto it : VT)
{
int v=it.second, t=it.first;
if(col[v])
{
S[head[v]].erase(idx[v]);
if(val[v])
{
int u=v;
while(1)
{
auto pt=S[head[u]].upper_bound(idx[u]);
if(pt==S[head[u]].begin()) u=par[head[u]];
else { u=invidx[*(--pt)]; break; }
}
if(u==now)
{
if(val[v]) te[val[v]]=t;
}
else
{
if(val[u]==0) val[u]=val[v];
else val[u]=uf.Union(val[u], val[v]);
}
val[v]=0;
}
col[v]=0;
}
else
{
S[head[v]].insert(idx[v]);
col[v]=1;
}
//for(auto it : V) if(it!=now) te[it]=te[uf.Find(it)];
}
for(auto it : V) if(it!=now) te[it]=te[uf.Find(it)];
}
void dfs2(int now, int bef, vector<int> &VV)
{
VV.push_back(now);
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
if(del[nxt.first]) continue;
dfs2(nxt.first, now, VV);
}
}
void decomp(int now)
{
int i, j;
getsz(now, now);
now=getcen(now, now, sz[now]);
getsz(now, now);
V.clear();
head[now]=now;
hld(now, now);
fs(now); fe(now);
//for(auto it : V) printf("%d : %d %d\n", it, ts[it], te[it]);
for(auto it : V) if(it!=now && ts[it]<=M) ans[now]++;
for(auto it : V) if(it!=now && te[it]>0) ans[it]++;
vector<int> VV;
for(auto it : V) if(it!=now) VV.push_back(ts[it]);
sort(VV.begin(), VV.end());
for(auto it : V) if(it!=now) ans[it]+=lower_bound(VV.begin(), VV.end(), te[it])-VV.begin();
for(auto nxt : adj[now])
{
if(del[nxt.first]) continue;
vector<int> chd, VVV;
dfs2(nxt.first, now, chd);
for(auto it : chd) VVV.push_back(ts[it]);
sort(VVV.begin(), VVV.end());
for(auto it : chd) ans[it]-=lower_bound(VVV.begin(), VVV.end(), te[it])-VVV.begin();
}
//for(auto it : V) printf("ANS %d : %d\n", it, ans[it]);
del[now]=true;
for(auto nxt : adj[now])
{
if(del[nxt.first]) continue;
decomp(nxt.first);
}
}
int main()
{
int i, j;
scanf("%d%d%d", &N, &M, &Q);
for(i=1; i<N; i++)
{
int u, v;
scanf("%d%d", &u, &v);
E[i]={u, v};
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
for(i=1; i<=M; i++)
{
int t;
scanf("%d", &t);
A[t].push_back(i);
}
for(i=1; i<N; i++) if(A[i].size()%2) A[i].push_back(M+1);
decomp(1);
for(i=1; i<=N; i++) ans[i]++;
while(Q--)
{
int t;
scanf("%d", &t);
printf("%d\n", ans[t]);
}
}
Compilation message
synchronization.cpp: In function 'void decomp(int)':
synchronization.cpp:221:6: warning: unused variable 'i' [-Wunused-variable]
int i, j;
^
synchronization.cpp:221:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
synchronization.cpp: In function 'int main()':
synchronization.cpp:263:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
synchronization.cpp:265:7: 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:269:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~
synchronization.cpp:277:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &t);
~~~~~^~~~~~~~~~
synchronization.cpp:287:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &t);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
19072 KB |
Output is correct |
| 2 |
Correct |
17 ms |
19200 KB |
Output is correct |
| 3 |
Correct |
17 ms |
19200 KB |
Output is correct |
| 4 |
Correct |
16 ms |
19200 KB |
Output is correct |
| 5 |
Correct |
16 ms |
19200 KB |
Output is correct |
| 6 |
Correct |
24 ms |
19456 KB |
Output is correct |
| 7 |
Correct |
115 ms |
21976 KB |
Output is correct |
| 8 |
Correct |
113 ms |
21856 KB |
Output is correct |
| 9 |
Correct |
120 ms |
21836 KB |
Output is correct |
| 10 |
Execution timed out |
8080 ms |
42828 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8076 ms |
48052 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
19200 KB |
Output is correct |
| 2 |
Correct |
16 ms |
19200 KB |
Output is correct |
| 3 |
Correct |
16 ms |
19200 KB |
Output is correct |
| 4 |
Correct |
16 ms |
19200 KB |
Output is correct |
| 5 |
Correct |
16 ms |
19200 KB |
Output is correct |
| 6 |
Correct |
28 ms |
19712 KB |
Output is correct |
| 7 |
Correct |
202 ms |
25188 KB |
Output is correct |
| 8 |
Execution timed out |
8071 ms |
53928 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8099 ms |
53720 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
19200 KB |
Output is correct |
| 2 |
Correct |
16 ms |
19200 KB |
Output is correct |
| 3 |
Correct |
15 ms |
19200 KB |
Output is correct |
| 4 |
Correct |
16 ms |
19200 KB |
Output is correct |
| 5 |
Correct |
23 ms |
19456 KB |
Output is correct |
| 6 |
Correct |
116 ms |
21980 KB |
Output is correct |
| 7 |
Execution timed out |
8090 ms |
42484 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
