ROOTTREE - Editorial

PROBLEM LINK:

Division 1
Division 2
Practice

Author: Anton Trygub
Tester: Alexander Morozov
Editorialist: Colin Galen

(My) video
Official video

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: https://youtu.be/TB_krkk_U9A?t=835
Official video: https://www.youtube.com/watch?v=Joezp9YzE5M

30 Likes

I rooted the node with the maximum outdegree because I thought that it will have more accessibility. Unfortunately, I only got 20 points with that.

5 Likes

Same here, bro. Anton Trygub rounds are absolute nightmares. But still love his contests. Our adhoc HERO! :wink:

3 Likes

LOL!! I don’t know why I got triggered after seeing the word tree. So, instead of doing this simple thing, I applied topological sort and then performed dfs in order to check the number of components. Answer would be the number -1.

5 Likes

After watching @galencolin’s CF and CC video editorials, I totally read this editorial in his voice.

6 Likes

Nice Problem ! Even tho i didn’t managed to solve it, but it’s good to learn some fresh new things

3 Likes

couldn’t solve A after a long time. learned lot.

Dude this solution was super cool, I overkilled the problem by finding the number of connected components in a toposort of the graph
My solution for anybody interested :

AC_CODE
#include <bits/stdc++.h>
using namespace std;
#define ar array 
struct digraph{
  int n ;
  vector<vector<int>>adj,adj2 ;
  digraph(int _n,vector<ar<int,2>> &e){
    n=_n ;
    adj=vector<vector<int>>(n);
    adj2=vector<vector<int>>(n);
    for(auto a:e){
      adj[a[0]].push_back(a[1]);
      adj2[a[1]].push_back(a[0]);
    }
  }
  vector<int>toposort(){
    queue<int>qu ;
    vector<int>ans ;
    vector<int>d(n) ;
    for(int i=0;i<n;i++){
      d[i]=adj2[i].size() ;
      if(!d[i])
        qu.push(i) ;
    }
    while(qu.size()){
      int u=qu.front() ;
      qu.pop() ;
      for(int x:adj[u]){
        --d[x] ;
        if(!d[x])
          qu.push(x) ;
      }
      ans.push_back(u) ;
    }
    if(ans.size()<n)
      ans.clear() ;
    return ans ;
  }
};
const int mxN=1e5 ;
int n;
vector<int>adj[mxN] ;
bool vis[mxN]  ;
void dfs(int v){
  vis[v]=1 ;
  for(int x:adj[v])
    if(!vis[x])
      dfs(x) ;
}
void solve(){ 
  cin >> n ;
  vector<ar<int,2>>e ;
  for(int i=0,u,v;i<n-1;i++){
    cin >> u >> v ; --u;--v ;
    adj[u].push_back(v); 
    e.push_back({u,v}) ;
  }
  digraph a(n,e) ;
  vector<int>ans=a.toposort();
  int ans1 =0 ;
  for(int i=0;i<n;i++)
    if(!vis[ans[i]])
      dfs(ans[i]),++ans1 ;
  cout << --ans1 << '\n' ;
  for(int i=0;i<n;i++)
    adj[i].clear() ;
  memset(vis,0,sizeof(vis));
}
signed main() {
  int t ;
  cin >> t ;
  while(t--)
    solve() ;
}

2 Likes

why cant we dfs on each node find the for all min(N-connectedComponentOfToEachNode)

2 Likes

Why should we even do that, explain a little bit about how you got this solution

each node we need to find the min Number of changes to make a Node rooted Node = number of nodes in tree - No of connected component @fireblaze_777

Are you talking about this please check it once i have tried the same.

https://www.codechef.com/viewsolution/38264002

1 Like

I was doing the same with DFS, but got WA and didn’t find why getting WA.
Can anybody help?
my code

1 Like

https://www.codechef.com/viewsolution/38264625 @galencolin (Can you please explain why these case fails )

yes

Nice Question

IF anyone Wants Hindi Editorial Video - Link

2 Likes

@galencolin your video is way better than the other one

1 Like

https://www.codechef.com/viewsolution/38219184
I am first finding the number of flips required if 1 is root , and then again did dfs to find for every node , and took minimum of it , someone please tell mistake .

1 Like

What was wrong with this approach?
What I tried to do was, we pick each vertex assuming it’s the root and run a dfs on it.
Suppose we are at node x right now in our dfs so we can visit all the nodes outgoing from x but then we also visit the nodes incoming to x and when we do that we do changes++.
And the answer should be the minimum of changes over all roots

1 Like

did the same thing…