#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5 , M = 2e5 + 5;
int n , m , q , ans[N] , dis[N] , sz[N];
vector <pair<int ,int>> adj[N];
vector <int> query , ch[N] , all , vec;
bool dead[N];
pair <int , int> tim[N];
struct nod{
int mx , lzy;
nod()
{
mx = 0;
lzy = 0;
}
} tree[M << 2];
void pdfs(int v , int p = -1)
{
sz[v] = 1;
for(auto uu : adj[v])
{
int u = uu.second;
if(u == p || dead[u])
continue;
pdfs(u , v);
sz[v] += sz[u];
}
}
int find_cent(int v , int val)
{
for(auto uu : adj[v])
{
int u = uu.second;
if(dead[u] || sz[u] > sz[v] || sz[u] <= val)
continue;
return find_cent(u , val);
}
return v;
}
void uplzy(int node , int lc , int rc)
{
if(tree[node].lzy == 0)
return;
int tmp = tree[node].lzy;
tree[lc].lzy += tmp;
tree[rc].lzy += tmp;
tree[lc].mx += tmp;
tree[rc].mx += tmp;
tree[node].lzy = 0;
}
int Get_first(int node = 1 , int nl = 0 , int nr = m)
{
if(nr - nl == 1)
return nl;
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(tree[lc].mx >= tree[rc].mx)
return Get_first(lc , nl , mid);
else
return Get_first(rc , mid , nr);
}
int Get_last(int node = 1 , int nl = 0 , int nr = m)
{
if(nr - nl == 1)
return nl;
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(tree[rc].mx >= tree[lc].mx)
return Get_last(rc , mid , nr);
else
return Get_last(lc , nl , mid);
}
void Add(int l , int r , int val , int node = 1 , int nl = 0 , int nr = m)
{
if(r <= nl || nr <= l)
return;
if(l <= nl && nr <= r)
{
tree[node].mx += val;
tree[node].lzy += val;
return;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
uplzy(node , lc , rc);
Add(l , r , val , lc , nl , mid); Add(l , r , val , rc , mid , nr);
tree[node].mx = max(tree[lc].mx , tree[rc].mx);
}
void add(int ed , int ty = 1)
{
for(int i = 0 ; i < ch[ed].size() ; i += 2)
Add(ch[ed][i] , ch[ed][i + 1] , ty);
}
void dfs(int v , int p = -1)
{
if(tree[1].mx < dis[v])
{
tim[v] = make_pair(-1 , -1);
return;
}
tim[v] = make_pair(Get_first() , Get_last());
for(auto uu : adj[v])
{
int u = uu.second , id = uu.first;
if(dead[u] || u == p)
continue;
add(id);
dfs(u , v);
add(id , -1);
}
}
void dfsp(int v , int p)
{
if(tim[v] == make_pair(-1 , -1))
return;
vec.push_back(v);
all.push_back(tim[v].first);
for(auto uu : adj[v])
{
int u = uu.second;
if(dead[u] || u == p)
continue;
dfsp(u , v);
}
}
void update(int v , int p , int ty = 1)
{
all.clear();
vec.clear();
dfsp(v , p);
sort(all.begin() , all.end());
for(auto u : vec)
{
int pos = upper_bound(all.begin() , all.end() , tim[u].second) - all.begin();
//cout << u << " " << tim[u].first << " " << tim[u].second << " " << ty * pos << endl;
ans[u] += ty * (pos);
}
}
void solve(int v)
{
pdfs(v);
int cent = find_cent(v , sz[v] / 2);
if(q == 1 && !dead[query.back()])
cent = query.back();
dis[cent] = 0;
dfs(cent);
//cout << v << " " << cent << endl;
update(cent , -1);
for(auto uu : adj[cent]) if(!dead[uu.second])
update(uu.second , cent , -1);
dead[cent] = true;
for(auto uu : adj[cent]) if(!dead[uu.second])
solve(uu.second);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m >> q;
for(int i = 1 ; i < n ; i++)
{
int u , v; cin >> u >> v;
adj[u].push_back({i , v});
adj[v].push_back({i , u});
}
for(int i = 0 ; i < m ; i++)
{
int x; cin >> x;
ch[x].push_back(i);
}
for(int i = 0 ; i < q ; i++)
{
int v; cin >> v; query.push_back(v);
}
for(int i = 1 ; i < n ; i++) if(ch[i].size() % 2 == 1)
ch[i].push_back(m);
solve(1);
for(auto u : query)
cout << ans[u] << '\n';
return 0;
}
Compilation message
synchronization.cpp: In function 'void add(int, int)':
synchronization.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int i = 0 ; i < ch[ed].size() ; i += 2)
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
11220 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
11276 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
626 ms |
25264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
11220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1782 ms |
29276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
11220 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
11220 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
