#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Pair{
int min, max;
Pair(){}
Pair(int min, int max): min(min), max(max){}
Pair operator+(const Pair &r)const{
return Pair(::min(min, r.min), ::max(max, r.max));
}
};
struct segTree{
Pair tree[800002];
int lazy[800002];
vector<vector<pair<int*, int> > > history;
void init(int i, int l, int r){
lazy[i] = -1;
if(l==r){
tree[i].min = tree[i].max = l;
return;
}
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
tree[i] = tree[i*2] + tree[i*2+1];
}
void save(){
history.push_back(vector<pair<int*, int> >());
}
void record(int &x){
history.back().push_back(make_pair(&x, x));
}
void record(Pair &x){
record(x.min), record(x.max);
}
void rollback(){
for(int i=(int)history.back().size()-1; i>=0; i--){
*(history.back()[i].first) = history.back()[i].second;
}
history.pop_back();
}
void propagate(int i, int l, int r){
if(lazy[i] == -1) return;
record(tree[i]);
tree[i] = Pair(lazy[i], lazy[i]);
if(l!=r){
record(lazy[i*2]);
record(lazy[i*2+1]);
lazy[i*2] = lazy[i*2+1] = lazy[i];
}
lazy[i] = -1;
}
void update(int i, int l, int r, int s, int e, int v){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
record(lazy[i]);
lazy[i] = v;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, v);
update(i*2+1, m+1, r, s, e, v);
record(tree[i]);
tree[i] = tree[i*2] + tree[i*2+1];
}
Pair query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return Pair(1e9, 0);
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e);
}
int lower_bound(int i, int l, int r, int x){
propagate(i, l, r);
if(tree[i].max < x) return r+1;
if(l==r) return l;
int m = (l+r)>>1;
propagate(i*2, l, m);
if(tree[i*2].max >= x) return lower_bound(i*2, l, m, x);
else return lower_bound(i*2+1, m+1, r, x);
}
};
struct Edge{
int x, y, idx;
Edge(){}
Edge(int x, int y, int idx): x(x), y(y), idx(idx){}
};
int n, m, q;
int ex[100002], ey[100002];
vector<Edge> link[100002];
int arr[200002];
int query[100002];
vector<int> toggle[100002];
int ans[100002];
int root;
bool centroidUsed[100002];
int subTreeSize[100002];
segTree tree;
int tn;
vector<int> timeList;
vector<int> adjList;
vector<int> subtreeList[100002];
int _g(int x){
return lower_bound(timeList.begin(), timeList.end(), x) - timeList.begin();
}
void dfsSubtree(int x, int p=-1){
subTreeSize[x] = 1;
for(Edge y: link[x]){
if(y.y==p || centroidUsed[y.y]) continue;
for(int t: toggle[y.idx]) timeList.push_back(t);
dfsSubtree(y.y, x);
subTreeSize[x] += subTreeSize[y.y];
}
}
int dfsFind(int x, int p, int lim){
for(auto y: link[x]){
if(y.y==p || centroidUsed[y.y]) continue;
if(subTreeSize[y.y] >= lim) return dfsFind(y.y, x, lim);
}
return x;
}
void dfsGetList(int x, int p, vector<int> &vec){
vec.push_back(x);
for(auto y: link[x]){
if(y.y==p || centroidUsed[y.y]) continue;
dfsGetList(y.y, x, vec);
}
}
int xtoc[100002], ctox[100002];
void update(int s, int e, int v){
s = tree.lower_bound(1, 0, tn, s);
e = tree.lower_bound(1, 0, tn, e+1) - 1;
tree.update(1, 0, tn, s, e, v);
}
void dfsdp1(int x, int p, int r){ /// x���� c�� �����ϴ� ���� ���� �ð��� ���
xtoc[x] = tree.query(1, 0, tn, 0, tn).min;
if(xtoc[x] != tn && x!=r) ans[r]++;
for(auto y: link[x]){
if(y.y==p || centroidUsed[y.y]) continue;
tree.save(); /// �� �ں��� ����Ʈ Ʈ���� �����Ѵ�
int prv = 0;
for(int i=0; i<(int)toggle[y.idx].size(); i+=2){
int sg = _g(toggle[y.idx][i]), eg = _g(toggle[y.idx][i+1]);
tree.update(1, 0, tn, prv, sg, tree.query(1, 0, tn, sg, sg).min);
prv = eg;
}
tree.update(1, 0, tn, prv, tn, tn);
dfsdp1(y.y, x, r); /// ���
tree.rollback(); /// �ѹ�
}
}
void dfsdp2(int x, int p=-1){ /// c���� x�� ����ϴ� ���� ���� �ð��� ���
ctox[x] = tree.lower_bound(1, 0, tn, tn) - 1;
if(ctox[x] != -1 && p!=-1) ans[x]++;
for(auto y: link[x]){
if(y.y==p || centroidUsed[y.y]) continue;
tree.save();
int prv = 0;
for(int i=0; i<(int)toggle[y.idx].size(); i+=2){
int sg = _g(toggle[y.idx][i]), eg = _g(toggle[y.idx][i+1]);
update(prv, sg, sg);
prv = eg;
}
update(prv, tn, tn);
dfsdp2(y.y, x);
tree.rollback();
}
}
int xtocvec[100005];
void findCentroid(int x){
/// ���� ��Ʈ���̵带 �����, �ð��� ���� ��ǥ ������ ����.
timeList.clear();
dfsSubtree(x);
x = dfsFind(x, -1, (subTreeSize[x]+1)/2);
centroidUsed[x] = 1;
timeList.push_back(1e9);
sort(timeList.begin(), timeList.end());
timeList.erase(unique(timeList.begin(), timeList.end()), timeList.end());
tn = (int)timeList.size()-1;
/// ���� ��Ʈ���̵忡 ������ �������� ��ϰ� �� �Ʒ��� ����Ʈ���� ����� �̾� ����.
adjList.clear();
for(Edge e: link[x]){
if(centroidUsed[e.y]) continue;
adjList.push_back(e.y);
subtreeList[e.y].clear();
dfsGetList(e.y, x, subtreeList[e.y]);
}
/// ���� ��Ʈ���̵忡������ dfs�� ���鼭, �� x�� ���� x->c�� �����ϴ� ���� ���� �ð��� ������.
tree.init(1, 0, tn);
dfsdp1(x, -1, x);
tree.init(1, 0, tn);
dfsdp2(x);
/// �ϼ��� ctox, xtoc �迭�� ���� ���� ������ �������. (c�� ���Ե� ���� ����)
for(Edge e: link[x]) if(!centroidUsed[e.y]) for(auto y: subtreeList[e.y]){
xtocvec[xtoc[y]]++;
}
for(int i=1; i<=tn; i++) xtocvec[i] += xtocvec[i-1];
for(Edge e: link[x]) if(!centroidUsed[e.y]) for(auto y: subtreeList[e.y]){
ans[y] += xtocvec[ctox[y]];
}
for(int i=tn; i>=1; i--) xtocvec[i] -= xtocvec[i-1];
for(Edge e: link[x]) if(!centroidUsed[e.y]) for(auto y: subtreeList[e.y]){
xtocvec[xtoc[y]]--;
}
for(Edge e: link[x]) if(!centroidUsed[e.y]){
vector<int> vec;
for(auto y: subtreeList[e.y]) vec.push_back(xtoc[y]);
sort(vec.begin(), vec.end());
for(auto y: subtreeList[e.y]){
ans[y] -= upper_bound(vec.begin(), vec.end(), ctox[y]) - vec.begin();
}
}
/// ����� �� ���͵��� ���� ����.
for(Edge e: link[x]){
subtreeList[e.y].clear();
subtreeList[e.y].shrink_to_fit();
}
/// ���� ��������� ����.
for(Edge e: link[x]){
if(centroidUsed[e.y]) continue;
findCentroid(e.y);
}
}
int main(){
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(Edge(ex[i], ey[i], i));
link[ey[i]].push_back(Edge(ey[i], ex[i], i));
}
for(int i=1; i<=m; i++){
scanf("%d", &arr[i]);
toggle[arr[i]].push_back(i);
}
for(int i=1; i<=q; i++) scanf("%d", &query[i]);
for(int i=1; i<n; i++) if(toggle[i].size() % 2) toggle[i].push_back(m+1);
for(int i=1; i<=n; i++) ans[i] = 1;
findCentroid(1);
for(int i=1; i<=q; i++){
printf("%d\n", ans[query[i]]);
}
}
Compilation message
synchronization.cpp: In function 'int main()':
synchronization.cpp:261:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
261 | scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:263:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
263 | scanf("%d %d", &ex[i], &ey[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:268:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
268 | scanf("%d", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~
synchronization.cpp:271:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
271 | for(int i=1; i<=q; i++) scanf("%d", &query[i]);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
962 ms |
202484 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 3 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 4 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 6 |
Correct |
40 ms |
10068 KB |
Output is correct |
| 7 |
Correct |
578 ms |
47280 KB |
Output is correct |
| 8 |
Runtime error |
412 ms |
262144 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
400 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
