-
Notifications
You must be signed in to change notification settings - Fork 0
Mo's on tree (Query on subtree)
YessineJallouli edited this page Nov 17, 2021
·
2 revisions
#include <bits/stdc++.h>
#define ll long long
#define SaveTime ios_base::sync_with_stdio(false), cin.tie(0);
using namespace std;
struct query {
int L,R,id;
query() {
L = R = id = 0;
}
query(int _L, int _R, int _id) {
L = _L;
R = _R;
id = _id;
}
};
int block;
bool cmp(query q1, query q2) {
if (q1.L/block < q2.L/block)
return true;
if (q1.L/block == q2.L/block && q1.R < q2.R)
return true;
return false;
}
const int N = 2e5+7;
vector<vector<int>> tree(N);
int tin[N];
int tout[N];
bool visited[N];
vector<int> tim;
void dfs(int node, int par = -1) {
tim.push_back(node);
tin[node] = tim.size()-1;
for (int ch : tree[node]) {
if (ch != par) {
dfs(ch, node);
}
}
tim.push_back(node);
tout[node] = tim.size()-1;
}
void ins(int id) {
// if the node is visited just return
}
void del(int id) {
}
int main() {
int n,q; cin >> n >> q;
block = 2*n/sqrt(q)+1;
for (int i = 0; i < n-1; i++) {
int a,b; cin >> a >> b;
tree[a].push_back(b);
tree[b].push_back(a);
}
dfs(1);
query qr[q];
for (int i = 0; i < q; i++) {
int node; cin >> node;
qr[i] = query(tin[node], tout[node], i);
}
sort(qr, qr+q, cmp);
int ans[q];
int l = 0, r = -1;
for (int i = 0; i < q; i++) {
auto [L,R,id] = qr[i];
while (r < R) {
r++;
ins(r);
}
while (r > R) {
del(r);
r--;
}
while (l < L) {
del(l);
l++;
}
while (l > L) {
l--;
ins(l);
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << '\n';
}
}