#include<stdio.h>
#include<assert.h>
#include<vector>
#include<string.h>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<string>
#include<iostream>
#include<set>
#include<unordered_set>
#include<map>
#include<queue>
#include<functional>
#include<list>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double, double> pdd;
typedef tuple<int,int,int> t3;
const int MX = 200005;
const int MM = 1000000007;
int st[MX], fin[MX], state[MX];
pii E[MX];
vector<pii> tmp[MX];
vector<t3> G[MX];
int a, b, c;
int vst[MX], cnt[MX], ans[MX];
int get_cnt(int x, int p){
if( vst[x] ) return cnt[x] = 0;
cnt[x] = 1;
for(t3 c : G[x]){
if( get<2>(c) == p ) continue;
cnt[x] += get_cnt(get<2>(c), x);
}
return cnt[x];
}
void get_pair(int x, int s, int e, int p, vector<t3> &R){
if( vst[x] ) return;
R.emplace_back(s, e, x);
for(t3 t : G[x]){
tie(a, b, c) = t;
if( c == p ) continue;
if( e < a ) continue;
get_pair(c, max(s, a), min(e, b), x, R);
}
}
struct BIT{
int t[MX];
void update(int x, int v){
while(x < MX) t[x] += v, x += x&-x;
}
int read(int x){
int r = 0;
while(x) r += t[x], x -= x&-x;
return r;
}
} tree;
void get_answer(vector<t3> &Q, int type){
sort(Q.begin(), Q.end());
reverse(Q.begin(), Q.end());
vector<int> L;
for(t3 e : Q){
tie(a, b, c) = e;
L.push_back(a);
}
sort(L.begin(), L.end());
for(t3 e : Q){
tie(a, b, c) = e;
int t = 0;
ans[c] += (t = lower_bound(L.begin(), L.end(), b) - L.begin()) * type;
// printf("add : %d, %d\n", c, t*type);
}
}
void solve(int x){
get_cnt(x, -1);
int r = x;
while(G[r].size()){
int mx = 0;
for(t3 c : G[r]) if( cnt[mx] < cnt[get<2>(c)] ) mx = get<2>(c);
if( cnt[mx]*2 <= cnt[r] ) break;
cnt[r] -= cnt[mx]; cnt[mx] += cnt[r]; r = mx;
}
// printf("%d\n", r);
vector<t3> Q, R;
for(t3 e : G[r]){
tie(a, b, c) = e;
get_pair(c, a, b, r, Q);
get_answer(Q, -1);
for(t3 t : Q){
int a, b, c;
tie(a, b, c) = t;
// printf("%d %d %d\n", a, b, c);
R.push_back(t);
}
// printf("\n");
Q.clear();
}
ans[r] += R.size() + 1;
get_answer(R, 1);
for(t3 t : R){
tie(a, b, c) = t;
ans[c]++;
}
vst[r] = 1;
for(t3 e : G[x]){
int c = get<2>(e);
if( !vst[c] ) solve(c);
}
}
int main()
{
int N, M, Q;
scanf("%d%d%d", &N, &M, &Q);
for(int i = 1; i < N; i++){
scanf("%d%d", &a, &b); E[i] = pii(a, b);
tmp[a].emplace_back(i, b);
tmp[b].emplace_back(i, a);
}
for(int i = 1; i <= M; i++){
scanf("%d", &a);
if( state[a] ) fin[a] = i;
else if( !st[a] ) st[a] = i;
state[a] ^= 1;
}
for(int i = 1; i < N; i++) if(state[i]) fin[i] = M+1;
for(int i = 1; i <= N; i++){
for(pii c : tmp[i]){
int a = c.second, b = i;
if( fin[c.first] != 0 && a != b ){
G[b].emplace_back(st[c.first], fin[c.first], a);
// printf("%d -> %d, %d~%d\n", b, a, st[c.first], fin[c.first]);
}
}
}
for(int i = 1; i <= N; i++){
if( vst[i] == 0 ) solve(i);
}
for(int i = 1; i <= Q; i++){
scanf("%d", &a);
printf("%d\n", ans[a]);
}
}
Compilation message
synchronization.cpp: In function 'int main()':
synchronization.cpp:130:29: 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:132:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b); E[i] = pii(a, b);
^
synchronization.cpp:137:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a);
^
synchronization.cpp:158:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
18432 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
18432 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
306 ms |
32892 KB |
Output is correct |
| 2 |
Correct |
273 ms |
32776 KB |
Output is correct |
| 3 |
Correct |
379 ms |
33936 KB |
Output is correct |
| 4 |
Correct |
386 ms |
33928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
18432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
203 ms |
24636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
18432 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
18432 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
