#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void input();
void solve();
void output();
int main(){
input();
solve();
output();
}
int n, m, q;
int ex[100002], ey[100002];
vector<pair<int, int> > link[100002];
vector<int> timings[100002];
int arr[200002];
int query[200002];
int ans[200002];
void input(){
scanf("%d %d %d", &n, &m, &q);
for(int i=1; i<n; i++){
scanf("%d %d", &ex[i], &ey[i]);
link[ex[i]].push_back(make_pair(ey[i], i));
link[ey[i]].push_back(make_pair(ex[i], i));
}
for(int i=1; i<=m; i++){
scanf("%d", &arr[i]);
timings[arr[i]].push_back(i);
}
for(int i=1; i<=q; i++) scanf("%d", &query[i]);
for(int i=1; i<n; i++) if((int)timings[i].size() % 2) timings[i].push_back(m);
}
bool centroidUsed[200002];
int subTreeSize[200002];
void dfs_subtreeSize(int x, int p){
subTreeSize[x] = 1;
for(auto y: link[x]){
if(centroidUsed[y.first] || y.first == p) continue;
dfs_subtreeSize(y.first, x);
subTreeSize[x] += subTreeSize[y.first];
}
}
int findCentroid(int x, int p, int lim){
for(auto y: link[x]){
if(centroidUsed[y.first] || y.first == p) continue;
if(subTreeSize[y.first] >= lim) return findCentroid(y.first, x, lim);
}
return x;
}
/// Union Find
struct UnionFind{
int par[100002];
void init(int _n){
for(int i=1; i<=n; i++) par[i] = i;
}
int find(int x){
if(x==par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
par[y] = x;
}
} dsu;
void dfsVertices(int x, int p, vector<int> &v){
v.push_back(x);
for(auto y: link[x]){
if(y.first == p || centroidUsed[y.first]) continue;
dfsVertices(y.first, x, v);
}
}
int inTime[100002];
void dfs_in(int x, int pe, map<int, int> &mp){
mp[1] = x;
for(auto y: link[x]){
if(centroidUsed[y.first] || y.second == pe || timings[y.second].empty()) continue;
map<int, int> mp2;
dfs_in(y.first, y.second, mp2);
if((int)mp.size() < (int)mp2.size()) mp.swap(mp2);
for(pair<int, int> p: mp2){
if(mp.find(p.first) != mp.end()) dsu.merge(mp[p.first], p.second);
else mp[p.first] = p.second;
}
mp2.clear();
}
for(int i=0; i<(int)timings[pe].size(); i+=2){
int s = timings[pe][i], ss = !i ? 0 : timings[pe][i-1] + 1;
/// [e, ee-1] 범위 내에 있는 모든 수를 합친다
if(mp.upper_bound(s) == mp.begin()) continue;
while(true){
auto it = prev(mp.upper_bound(s));
if(it == mp.begin() || prev(it)->first < ss) break;
dsu.merge(it->second, prev(it)->second);
mp.erase(prev(it));
}
auto it = prev(mp.upper_bound(s));
int x = it->second;
mp.erase(it);
mp[s] = x;
}
while(!mp.empty() && mp.rbegin()->first > timings[pe].back()) mp.erase(prev(mp.end()));
//printf("Dfs_in %d: ", x);
//for(pair<int, int> p: mp) printf("(%d, %d) ", p.first, p.second);
//puts("");
}
int outTime[100002];
void dfs_out(int x, int pe, map<int, int> &mp){
mp[m] = x;
for(auto y: link[x]){
if(centroidUsed[y.first] || y.second == pe || timings[y.second].empty()) continue;
map<int, int> mp2;
dfs_out(y.first, y.second, mp2);
if((int)mp.size() < (int)mp2.size()) mp.swap(mp2);
for(pair<int, int> p: mp2){
if(mp.find(p.first) != mp.end()) dsu.merge(mp[p.first], p.second);
else mp[p.first] = p.second;
}
mp2.clear();
}
for(int i=0; i<(int)timings[pe].size(); i+=2){
int e = timings[pe][i+1], ee = (i+2 == (int)timings[pe].size()) ? m+1 : timings[pe][i+2] - 1;
/// [e, ee-1] 범위 내에 있는 모든 수를 합친다
if(mp.lower_bound(e) == mp.end()) continue;
while(true){
auto it = mp.lower_bound(e);
if(next(it) == mp.end() || next(it)->first > ee) break;
dsu.merge(it->second, next(it)->second);
mp.erase(next(it));
}
auto it = mp.lower_bound(e);
int x = it->second;
mp.erase(it);
mp[e] = x;
}
while(!mp.empty() && mp.begin()->first < timings[pe][0]) mp.erase(mp.begin());
//printf("Dfs_out %d: ", x);
//for(pair<int, int> p: mp) printf("(%d, %d) ", p.first, p.second);
//puts("");
}
vector<int> subtree[100002], subTreeIn[100002], subTreeOut[100002];
void calculateInCentroid(int c){
vector<int> vertices;
dfsVertices(c, -1, vertices);
for(int x: vertices){
dsu.par[x] = x, inTime[x] = m+1, outTime[x] = 0;
subtree[x].clear(), subTreeIn[x].clear(), subTreeOut[x].clear();
}
vector<int> inT, outT;
/// x -> c로 들어오는 시점 찾기
inTime[c] = 1;
for(auto y: link[c]){
if(centroidUsed[y.first]) continue;
dfsVertices(y.first, c, subtree[y.first]);
map<int, int> mp;
for(int x: subtree[y.first]) dsu.par[x] = x;
if(!timings[y.second].empty()) dfs_in(y.first, y.second, mp);
for(pair<int, int> p: mp) inTime[p.second] = p.first;
for(int x: subtree[y.first]){
inTime[x] = inTime[dsu.find(x)];
subTreeIn[y.first].push_back(inTime[x]);
inT.push_back(inTime[x]);
}
mp.clear();
for(int x: subtree[y.first]) dsu.par[x] = x;
if(!timings[y.second].empty()) dfs_out(y.first, y.second, mp);
for(pair<int, int> p: mp) outTime[p.second] = p.first;
for(int x: subtree[y.first]){
outTime[x] = outTime[dsu.find(x)];
subTreeOut[y.first].push_back(outTime[x]);
outT.push_back(outTime[x]);
}
}
inTime[c] = 1, outTime[c] = m;
inT.push_back(1), outT.push_back(m);
//printf("Centroid is %d\n", c);
//for(int v: vertices) printf("Vertex %d: in %d, out %d\n", v, inTime[v], outTime[v]);
/// 정렬
sort(inT.begin(), inT.end());
sort(outT.begin(), outT.end());
for(int x: vertices){
sort(subTreeIn[x].begin(), subTreeIn[x].end());
sort(subTreeOut[x].begin(), subTreeOut[x].end());
}
/// 센트로이드 답 업데이트
ans[c] += upper_bound(inT.begin(), inT.end(), m) - inT.begin();
/// 각 정점 답 업데이트
for(auto y: link[c]){
if(centroidUsed[y.first]) continue;
for(int x: subtree[y.first]){
ans[x] += upper_bound(inT.begin(), inT.end(), outTime[x]) - inT.begin();
ans[x] -= upper_bound(subTreeIn[y.first].begin(), subTreeIn[y.first].end(), outTime[x]) - subTreeIn[y.first].begin();
}
}
}
void centroidDecomposition(int x){
dfs_subtreeSize(x, -1);
x = findCentroid(x, -1, (subTreeSize[x] + 1) / 2);
centroidUsed[x] = 1;
calculateInCentroid(x);
for(auto y: link[x]){
if(centroidUsed[y.first]) continue;
centroidDecomposition(y.first);
}
}
void solve(){
centroidDecomposition(1);
}
void output(){
for(int i=1; i<=q; i++) printf("%d\n", ans[query[i]]);
}
Compilation message
synchronization.cpp: In function 'void input()':
synchronization.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
26 | scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | scanf("%d %d", &ex[i], &ey[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | scanf("%d", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~
synchronization.cpp:36:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | for(int i=1; i<=q; i++) scanf("%d", &query[i]);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
12048 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
484 ms |
49788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
365 ms |
58476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
12008 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
