PROBLEM LINK:
Division 1
Division 2
Practice
Author: Anton Trygub
Tester: Alexander Morozov
Editorialist: Colin Galen
DIFFICULTY:
Easy
PREREQUISITES:
Graphs, Trees
PROBLEM:
You’re given a directed tree (if the graph was undirected, the edges would form a tree) with n vertices. You want to give this tree a “root” - a vertex r where you can reach all other vertices by traversing some edges starting from r. You can perform some number of the following operation: remove some edge, then add another edge such that the graph remains a directed tree. Find the mininum required number of such operations to root the tree.
QUICK EXPLANATION:
Subtask 1
Either the final root will be vertex 1 (the center of the star), or some other vertex v. In the first case, the answer is the indegree of the center. In the second case, that node must point toward the star and the star must point to every other vertex, so the answer is the cost of flipping the edge 1 \to v if necessary, plus the cost of flipping all other edges to point away from 1.
Main solution
The only condition is that each vertex must have indegree \leq 1. One operation can decrease the indegree of exactly one vertex by 1, so the required number of operations is the number of operations to decrease each indegree to a number \leq 1, which can be summarized as \displaystyle \sum_{i = 1}^{n}{max(indegree[i] - 1, 0)}.
EXPLANATION:
Subtask 1
Either the final root will be vertex 1 (the center of the star), or some other vertex v. Let’s consider both cases separately.
In the first case, the answer is the indegree of the center 1, since everything has to be outgoing from the center. You can flip an edge in 1 operation, and you can’t do better because either you have to connect the newly detached vertex (from removing the edge) to the center, or to some other vertex, but either way it essentially only affects that vertex.
In the second case, that vertex v must point toward the star and the star must point to every other vertex, so the answer is the cost of flipping the edge 1 \to v if necessary, plus the cost of flipping all other edges to point away from 1. This can be done in O(1) for each v with a bit of casework.
The final answer is the minimum over both cases.
Main solution
One commonly used property of trees is that every vertex except the root has exactly one parent. If we consider the final, rooted tree that we’ll get after some operations, this will also be true in the directed version. Indeed, if any vertex has more than one parent, you wouldn’t be able to move from one parent to another, and thus the tree wouldn’t be rooted.
If every vertex except the root has one parent, then the tree is also automatically rooted.
Proof
Consider any vertex v. Either v is the root, or it has a parent. In the second case, we can set v to v's parent and restart the process. Because the graph is a directed tree, there are no cycles, so we’ll never visit any vertex multiple times. Thus, this process will eventually stop at the root, meaning we can reach v from the root through that sequence of edges.
So this condition is both necessary and sufficient for the tree being rooted.
Any parent of a vertex v, by the definition of the problem, has an edge directed toward v. If a vertex has more than one parent, then its indegree - the number of edges that go into it - will be greater than 1. So in the final tree, we need all indegrees to be at most 1 (the root itself will have indegree 0). Note that it’s not possible for more than one vertex to have indegree 0 in the final tree, because if so, we can use the pigeonhole principle to show that some other vertex has indegree > 1.
So we need to decrease the indegree of each vertex to \leq 1. When we remove an edge, it decreases the indegree of exactly one vertex by 1, so the required number of operations is either 0 if the indegree is already \leq 1, or the indegree minus 1 if we need to do some operations on it. This can be succinctly written as \max(indegree - 1, 0), and the answer is the sum of this quantity over all vertices.
The final part is showing that the new edges we introduce don’t create more operations we have to do. If we reverse the pigeonhole principle, we can show that if we have a vertex with indegree > 1, we have at least two with indegree 0. So we can create an edge that goes into one of those vertices and points from some vertex in the other component we got from removing the edge, not creating extra operations we have to do in the future.
TIME COMPLEXITY:
Subtask 1
O(n) for reading in the input, computing the star, and computing all other vertices (O(1) each).
Main solution
O(n) for reading in the input and computing indegrees.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
vector<int> in(n);
for (int i = 0; i<n-1; i++)
{
int u, v;
cin>>u>>v;
u--; v--;
in[v]++;
}
int cnt = 0;
for (auto it: in) if (it==0) cnt++;
cout<<cnt-1<<endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int t; cin>>t;
while (t--) solve();
}
Note that counting 0's is equivalent to counting edges we need to remove, because we also have the constraint that the final array of degrees has exactly one 0.
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
using nagai = long long;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector<int>in(n), out(n);
for(int i=0;i<n-1;++i) {
int a, b;
cin >> a >> b;
--a, --b;
++out[a];
++in[b];
}
sort(in.begin(),in.end());
int ans = in.front();
for(int i=1;i<n;++i)
ans += max(0, in[i] - 1);
cout << ans << '\n';
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL); cout.tie(NULL);}
typedef long long ll;
void solve(int tc = 0) {
ll n;
cin >> n;
ll id[n] = {0};
for (ll i = 0; i < n - 1; i++) {
ll x, y;
cin >> x >> y;
--x; --y;
++id[y];
}
ll ans = 0;
for (ll i = 0; i < n; i++) ans += max(0LL, id[i] - 1);
cout << ans << '\n';
}
int main() {
send help
int tc = 1;
cin >> tc;
for (int t = 0; t < tc; t++) solve(t);
}
Video Editorial(s)
My video: CodeChef September Lunchtime 2020 - All Solutions (Div. 1 + Div. 2) - YouTube
Official video: - YouTube
