This is my personal note and might be some kind of user editorial/learning material for some people!↵
↵
This is the fourth episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), which are solved without looking at the editorial, that are both interesting and educational. I normally will spend a few hours on each problem so **please be patient** when reading the blog. The problem on these notes should give a very interesting solution and will likely be optimizations problems (I feel like these problems have an IOI-style, which requires you to find some incomplete solution first then find the final solution using it).↵
↵
If you want to motivate me to write a continuation (aka note 5), a **significant upvote from you** would be well appreciated! If I received lots of downvotes (because I'm also spending a lot of time to write this and to learn latex only to express my ideas accurately to you guys), I'm probably not gonna continuing writing these blogs.↵
↵
[Problem link](https://codeforces.me/problemset/problem/613/D)↵
↵
Problem statement: ↵
↵
Given a tree with $N$ nodes. You are given $Q$ queries. For each query, you are given an integer $K$ and an array $\{a\}$ of length $K$. ↵
↵
We will color all these nodes in $\{a\}$ in red.↵
↵
$\sum_{i=1}^{Q}K_{i} \leq 10^5, 1 \leq N,Q\leq 10^5$.↵
↵
Enemies will try to disconnect these nodes by removing other nodes that are not in $\{a\}$. Find minimum nodes (that are not in $\{a\}$) removed in order to disconnect those nodes in $\{a\}$. Queries are not permanent (the nodes destroyed will be resetted after the query).↵
↵
<spoiler summary="Tags">↵
HLD/binary lifting for finding LCA, dfs, virtual tree↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Does every node from $1$ to $N$ matter in a query? ↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Definitely not all nodes matter. Only the $LCA$ of nodes in $\{a\}$ and the nodes in $\{a\}$ matters.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
This completely satisfies the condition of building virtual trees.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
If we traverse through the nodes in the virtual tree, there will be three conditions:↵
↵
1) If we are at a non-red node and we have $\geq 2$ children that is red?↵
↵
2) If we are at a non-red node and we have only $1$ child that is red?↵
↵
3) If we are at a red node?↵
↵
</spoiler>↵
↵
Are you able to find the full solution from the hints?↵
↵
<spoiler summary="Solution">↵
Let us build a virtual tree based on the nodes. There are many blogs that show how to do this. If you need a template of building a virtual tree, you can DM me for it.↵
↵
Let us dfs from the root of the virtual tree. ↵
↵
1) If we are at a non-red node and we have $\geq 2$ children? This means that we should just break the node here. ↵
↵
2) If we are at a non-red node and we have only $1$ child that is red? We can simply color current node red.↵
↵
3) If we are at a red node? From the second condition, we can simply count the number of children that are red and add it to the answer. ↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include<bits/stdc++.h>↵
using namespace std;↵
using i64 = long long;↵
↵
const int _N = 2e5;↵
vector<int> G[_N];↵
namespace shupou {↵
int dfn[_N], tim = 0, dep[_N], sz[_N], fa[_N], top[_N], son[_N];↵
void dfs_heavy(int u, int f) {↵
dfn[u] = ++tim; sz[u] = 1; fa[u] = f; dep[u] = dep[f] + 1;↵
for (auto& v : G[u]) {↵
if (v == f) continue;↵
dfs_heavy(v, u);↵
sz[u] += sz[v];↵
if (sz[v] > sz[son[u]]) son[u] = v;↵
}↵
}↵
void dfs_top(int u, int f) {↵
top[u] = f;↵
if (son[u]) dfs_top(son[u], f);↵
for (auto& v : G[u]) {↵
if (v == fa[u] || v == son[u]) continue;↵
dfs_top(v, v);↵
}↵
}↵
int lca(int x, int y) {↵
while (top[x] != top[y]) {↵
if (dep[top[x]] >= dep[top[y]]) x = fa[top[x]];↵
else y = fa[top[y]];↵
}↵
return dep[x] < dep[y] ? x : y;↵
}↵
void shupou(int root = 1) {↵
dfs_heavy(root, 0);↵
dfs_top(root, root);↵
}↵
};↵
namespace xushu {↵
int a[_N], pt = 0, npt = 0;↵
vector<int> XG[_N], prev;↵
int cmp(int x, int y) { return shupou::dfn[x] < shupou::dfn[y]; }↵
void build(vector<int>& x) {↵
pt = 0;↵
for (auto& v : x) a[++pt] = v;↵
sort(a + 1, a + pt + 1, cmp);↵
npt = pt;↵
for (int i = 2; i <= pt; i++) {↵
int lca = shupou::lca(a[i], a[i - 1]);↵
if (lca != a[i] && lca != a[i - 1]) a[++npt] = lca;↵
}↵
sort(a + 1, a + npt + 1);↵
npt = unique(a + 1, a + npt + 1) - (a + 1);↵
sort(a + 1, a + npt + 1, cmp);↵
prev.push_back(a[1]);↵
for (int i = 2; i <= npt; i++) {↵
int lca = shupou::lca(a[i], a[i - 1]);↵
XG[lca].push_back(a[i]);↵
prev.push_back(a[i]);↵
}↵
}↵
void clear() {↵
for (auto& v : prev) XG[v].clear();↵
prev.clear();↵
pt = 0; npt = 0;↵
}↵
};↵
bool red[_N];↵
int dfs(int u) {↵
int ans = 0;↵
for (auto& v : xushu::XG[u]) ans += dfs(v);↵
if (red[u]) {↵
for (auto& v : xushu::XG[u])↵
if (red[v]) ans++;↵
}↵
else {↵
int cnt = 0;↵
for (auto& v : xushu::XG[u])//if current = not important city↵
if (red[v]) cnt++;↵
if (cnt > 1) ans++;//if we have >= 2 cities meaning we must break here↵
if (cnt == 1) red[u] = true; //or else just make it red and just go up↵
}↵
return ans;↵
}↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr); cout.tie(nullptr);↵
↵
int N; cin >> N;↵
for (int i = 1; i <= N - 1; i++) {↵
int u, v; cin >> u >> v;↵
G[u].push_back(v);↵
G[v].push_back(u);↵
}↵
shupou::shupou();↵
int Q; cin >> Q;↵
while (Q--) {↵
int M; cin >> M;↵
vector<int> p(M);↵
bool neighbour = false;↵
for (int i = 0; i < M; i++) {↵
cin >> p[i];↵
red[p[i]] = true;↵
}↵
for (int i = 0; i < M; i++) ↵
if (red[shupou::fa[p[i]]] == true)//if its father is red and current node is also red, it can never be colored↵
neighbour = true;↵
↵
if (neighbour) { //if it is impossible to disconnect them↵
cout << "-1\n";↵
for (int i = 0; i < M; i++) red[p[i]] = false;↵
continue;↵
}↵
else {↵
xushu::build(p); //build the virtual tree↵
cout << dfs(xushu::a[1]) << '\n'; //dfs from root of the virtual tree↵
for (auto& x : xushu::prev) red[x] = false; //reset all to without color↵
xushu::clear(); //clear the virtual tree↵
}↵
}↵
}↵
↵
```↵
</spoiler>↵
↵
<spoiler summary="Feelings">↵
I've first heard about virtual trees around 3/4 months ago during a camp for preparation of IOI 2023. This the first problem I've seen that is solved using virtual tree. Amazing problem (also introduction to virtual trees), but I used 4/5 hours on solving 1 problem only. It took me too long to implement virtual tree. Also, I think the problem rating is rated too high, maybe because virtual tree is not well known back then.↵
</spoiler>↵
↵
↵
This is the fourth episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), which are solved without looking at the editorial, that are both interesting and educational. I normally will spend a few hours on each problem so **please be patient** when reading the blog. The problem on these notes should give a very interesting solution and will likely be optimizations problems (I feel like these problems have an IOI-style, which requires you to find some incomplete solution first then find the final solution using it).↵
↵
If you want to motivate me to write a continuation (aka note 5), a **significant upvote from you** would be well appreciated! If I received lots of downvotes (because I'm also spending a lot of time to write this and to learn latex only to express my ideas accurately to you guys), I'm probably not gonna continuing writing these blogs.↵
↵
[Problem link](https://codeforces.me/problemset/problem/613/D)↵
↵
Problem statement: ↵
↵
Given a tree with $N$ nodes. You are given $Q$ queries. For each query, you are given an integer $K$ and an array $\{a\}$ of length $K$. ↵
↵
We will color all these nodes in $\{a\}$ in red.↵
↵
$\sum_{i=1}^{Q}K_{i} \leq 10^5, 1 \leq N,Q\leq 10^5$.↵
↵
Enemies will try to disconnect these nodes by removing other nodes that are not in $\{a\}$. Find minimum nodes (that are not in $\{a\}$) removed in order to disconnect those nodes in $\{a\}$. Queries are not permanent (the nodes destroyed will be resetted after the query).↵
↵
<spoiler summary="Tags">↵
HLD/binary lifting for finding LCA, dfs, virtual tree↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Does every node from $1$ to $N$ matter in a query? ↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Definitely not all nodes matter. Only the $LCA$ of nodes in $\{a\}$ and the nodes in $\{a\}$ matters.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
This completely satisfies the condition of building virtual trees.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
If we traverse through the nodes in the virtual tree, there will be three conditions:↵
↵
1) If we are at a non-red node and we have $\geq 2$ children that is red?↵
↵
2) If we are at a non-red node and we have only $1$ child that is red?↵
↵
3) If we are at a red node?↵
↵
</spoiler>↵
↵
Are you able to find the full solution from the hints?↵
↵
<spoiler summary="Solution">↵
Let us build a virtual tree based on the nodes. There are many blogs that show how to do this. If you need a template of building a virtual tree, you can DM me for it.↵
↵
Let us dfs from the root of the virtual tree. ↵
↵
1) If we are at a non-red node and we have $\geq 2$ children? This means that we should just break the node here. ↵
↵
2) If we are at a non-red node and we have only $1$ child that is red? We can simply color current node red.↵
↵
3) If we are at a red node? From the second condition, we can simply count the number of children that are red and add it to the answer. ↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```cpp↵
#include<bits/stdc++.h>↵
using namespace std;↵
using i64 = long long;↵
↵
const int _N = 2e5;↵
vector<int> G[_N];↵
namespace shupou {↵
int dfn[_N], tim = 0, dep[_N], sz[_N], fa[_N], top[_N], son[_N];↵
void dfs_heavy(int u, int f) {↵
dfn[u] = ++tim; sz[u] = 1; fa[u] = f; dep[u] = dep[f] + 1;↵
for (auto& v : G[u]) {↵
if (v == f) continue;↵
dfs_heavy(v, u);↵
sz[u] += sz[v];↵
if (sz[v] > sz[son[u]]) son[u] = v;↵
}↵
}↵
void dfs_top(int u, int f) {↵
top[u] = f;↵
if (son[u]) dfs_top(son[u], f);↵
for (auto& v : G[u]) {↵
if (v == fa[u] || v == son[u]) continue;↵
dfs_top(v, v);↵
}↵
}↵
int lca(int x, int y) {↵
while (top[x] != top[y]) {↵
if (dep[top[x]] >= dep[top[y]]) x = fa[top[x]];↵
else y = fa[top[y]];↵
}↵
return dep[x] < dep[y] ? x : y;↵
}↵
void shupou(int root = 1) {↵
dfs_heavy(root, 0);↵
dfs_top(root, root);↵
}↵
};↵
namespace xushu {↵
int a[_N], pt = 0, npt = 0;↵
vector<int> XG[_N], prev;↵
int cmp(int x, int y) { return shupou::dfn[x] < shupou::dfn[y]; }↵
void build(vector<int>& x) {↵
pt = 0;↵
for (auto& v : x) a[++pt] = v;↵
sort(a + 1, a + pt + 1, cmp);↵
npt = pt;↵
for (int i = 2; i <= pt; i++) {↵
int lca = shupou::lca(a[i], a[i - 1]);↵
if (lca != a[i] && lca != a[i - 1]) a[++npt] = lca;↵
}↵
sort(a + 1, a + npt + 1);↵
npt = unique(a + 1, a + npt + 1) - (a + 1);↵
sort(a + 1, a + npt + 1, cmp);↵
prev.push_back(a[1]);↵
for (int i = 2; i <= npt; i++) {↵
int lca = shupou::lca(a[i], a[i - 1]);↵
XG[lca].push_back(a[i]);↵
prev.push_back(a[i]);↵
}↵
}↵
void clear() {↵
for (auto& v : prev) XG[v].clear();↵
prev.clear();↵
pt = 0; npt = 0;↵
}↵
};↵
bool red[_N];↵
int dfs(int u) {↵
int ans = 0;↵
for (auto& v : xushu::XG[u]) ans += dfs(v);↵
if (red[u]) {↵
for (auto& v : xushu::XG[u])↵
if (red[v]) ans++;↵
}↵
else {↵
int cnt = 0;↵
for (auto& v : xushu::XG[u])//if current = not important city↵
if (red[v]) cnt++;↵
if (cnt > 1) ans++;//if we have >= 2 cities meaning we must break here↵
if (cnt == 1) red[u] = true; //or else just make it red and just go up↵
}↵
return ans;↵
}↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr); cout.tie(nullptr);↵
↵
int N; cin >> N;↵
for (int i = 1; i <= N - 1; i++) {↵
int u, v; cin >> u >> v;↵
G[u].push_back(v);↵
G[v].push_back(u);↵
}↵
shupou::shupou();↵
int Q; cin >> Q;↵
while (Q--) {↵
int M; cin >> M;↵
vector<int> p(M);↵
bool neighbour = false;↵
for (int i = 0; i < M; i++) {↵
cin >> p[i];↵
red[p[i]] = true;↵
}↵
for (int i = 0; i < M; i++) ↵
if (red[shupou::fa[p[i]]] == true)//if its father is red and current node is also red, it can never be colored↵
neighbour = true;↵
↵
if (neighbour) { //if it is impossible to disconnect them↵
cout << "-1\n";↵
for (int i = 0; i < M; i++) red[p[i]] = false;↵
continue;↵
}↵
else {↵
xushu::build(p); //build the virtual tree↵
cout << dfs(xushu::a[1]) << '\n'; //dfs from root of the virtual tree↵
for (auto& x : xushu::prev) red[x] = false; //reset all to without color↵
xushu::clear(); //clear the virtual tree↵
}↵
}↵
}↵
↵
```↵
</spoiler>↵
↵
<spoiler summary="Feelings">↵
I've first heard about virtual trees around 3/4 months ago during a camp for preparation of IOI 2023. This the first problem I've seen that is solved using virtual tree. Amazing problem (also introduction to virtual trees), but I used 4/5 hours on solving 1 problem only. It took me too long to implement virtual tree. Also, I think the problem rating is rated too high, maybe because virtual tree is not well known back then.↵
</spoiler>↵
↵
