#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int>> g;
namespace centroid{
int node_active_cnt = 0;
struct node{
bool built = false;
vector<pair<int, int>> par_bid;
int active_cnt = 0;
vector<int> branch_cnt;
void update(int bid, int value){
node_active_cnt -= active_cnt >= 2;
active_cnt -= !!branch_cnt[bid];
branch_cnt[bid] += value;
active_cnt += !!branch_cnt[bid];
node_active_cnt += active_cnt >= 2;
}
};
vector<node> a;
vector<int> tsz;
void dfs_size(int v, int p){
tsz[v] = 1;
for (int u: g[v]){
if (a[u].built || u == p) continue;
tsz[v] += tsz[u];
}
}
int dfs_find_cen(int v, int p, int rq){
for (int u: g[v]){
if (a[u].built || u == p) continue;
if (tsz[u] >= rq) return dfs_find_cen(u, v, rq);
}
return v;
}
void dfs_mark_branch(int v, int p, int cen, int b){
a[v].par_bid.emplace_back(cen, b);
for (int u: g[v]){
if (a[u].built || u == p) continue;
dfs_mark_branch(u, v, cen, b);
}
}
void dfs_centroid(int v){
dfs_size(v, -1);
int cen = dfs_find_cen(v, -1, (tsz[v]+1) / 2);
v = -1;
a[cen].par_bid.emplace_back(cen, 0);
a[cen].par_bid.emplace_back(cen, 1);
a[cen].branch_cnt.emplace_back();
a[cen].branch_cnt.emplace_back();
for (int u: g[cen]){
if (a[u].built) continue;
dfs_mark_branch(u, cen, cen, a[cen].branch_cnt.size());
a[cen].branch_cnt.emplace_back();
}
a[cen].built = true;
for (int u: g[cen]){
if (a[u].built) continue;
cout << "CEN: " << cen << " " << u << "\n";
dfs_centroid(u);
}
}
void init(){
a.resize(g.size());
tsz.resize(g.size());
dfs_centroid(0);
}
void modify_node(int v, int value){
for (pair<int, int> par: a[v].par_bid){
a[par.first].update(par.second, value);
}
}
}
vector<int> c;
const int SQRT = 300;
struct query{
int l, r, idx;
friend bool operator<(const query &a, const query &b){
int blocka = a.l / SQRT, blockb = b.l / SQRT;
if (blocka != blockb) return blocka < blockb;
if (blocka % 2 == 0) return a.r < b.r;
else return a.r > b.r;
}
};
namespace query_state{
int l=0, r=-1;
int move_query(int nl, int nr){
while (r < nr){
r++;
centroid::modify_node(c[r], 1);
}
while (l > nl){
l--;
centroid::modify_node(c[l], 1);
}
while (r > nr){
centroid::modify_node(c[r], -1);
r--;
}
while (l < nl){
centroid::modify_node(c[l], -1);
l++;
}
return centroid::node_active_cnt;
}
};
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n, m, q; cin >> n >> m >> q;
g.resize(n);
for (int i=1; i<n; i++){
int a, b; cin >> a >> b;
a--, b--;
g[a].push_back(b);
g[b].push_back(a);
}
centroid::init();
c.resize(m);
for (int i=0; i<m; i++){
cin >> c[i];
c[i]--;
}
// vector<query> qrs(q);
// for (int i=0; i<qrs.size(); i++){
// cin >> qrs[i].l >> qrs[i].r;
// qrs[i].l--, qrs[i].r--;
// qrs[i].idx = i;
// }
// sort(qrs.begin(), qrs.end());
// vector<int> result(q);
// for (const query &cq: qrs){
// result[cq.idx] = query_state::move_query(cq.l, cq.r);
// }
// for (int i=0; i<result.size(); i++){
// cout << result[i] << "\n";
// }
for (int i=0; i<q; i++){
int l, r; cin >> l >> r;
l--, r--;
cout << query_state::move_query(l, r) << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
