BINODE - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Adarsh Kumar Sinha

DIFFICULTY:

MEDIUM-HARD.

PREREQUISITES:

Graphs, Dynamic Programming

Short Explanation

In order to traverse through the longest path, Binod needs to choose the Diameter of the tree.

Detailed Explanation

Binod will choose the diameter of the tree (made out of areas as nodes and roads as edges) as his path. We will then calculate the length of the Diameter of the tree and find how many roads (edges) we had to traverse through, lets call this D. The number of areas thus covered will be D+1. If this is Even, answer is Yes, else No. We will discuss two different ways of finding this Diameter.

SIMPLER APPROACH :

A better and simpler approach, is to do DFS two times. This method always work in finding the Diameter of the tree. In first DFS we find the farthest node from any chosen Node, lets call this Node N1. During the second DFS call, we find the farthest Node from the Node D1, and the distance of this farthest node from node N1 is the diameter of the tree.

Finding the Diameter of the Tree using DP

One way of finding the diameter of a tree is doing a Depth First Search (DFS) on each node and find the arithmetically highest depth. This method however may fail here, because of the Time Constraints. This method costs us O(N*N).
In order to solve this in O(N), we will consider a dynamic programming method to solve this problem. Each time we choose a node, we can either consider as a part of the diameter of the tree, or Not.
Before proceeding forward, we will define another term as downpath. This downpath vector/list stores the maximum reachable depth from each Node, i.e, downpath[i] stores the maximum reachable depth in the tree if we consider the Node i as our parent Node. Note that already traversed nodes, or the parent nodes of the Node i should not be considered in the depth as we look for downpath[i].

Now coming back to our DP solution, we either had an option to make the Node i as a part of the diameter, or not to make it. Lets denote this DP state as dp[src][B], where src denotes the current Node, and B=0 means not taking this node as a node in diameter, and B=1 means taking this node as a node in diameter.

Lets consider the case a: We chose the node ‘src’ as our current node, and for this case B=0, as we are not considering this node as part of our Diameter. So, if we do not take this node as our Diameter, we will look for the Diameter in the subtrees of Node ‘src’. Hence to fill dp[src][0], we will iterate through each of the child nodes of ‘src’ considering them as the parent node of the the subtrees of node ‘src’. Hence, while iterating through all dp[child][0], we will store the maximum in the dp[src][0]. Hence dp[src][0] was calculated.

case ‘b’ : We consider the current node 'src’ as a node in our Diameter. If we do that, it is easy to visualize that now will just need to add two maximum downpath-s possible from at most any two children nodes of Node ‘src’. Hence, when we are calculating dp[src][1], we will store the downpaths of the children of src, sort them, and take the two maximum values available and merge them with dp[src][1].

Final Call

As we have defined our DP states. Now its time to call for the Diameter. To get the diameter of the tree we can consider any node as our Root node, and make the call. As from the above discussion it is clear, that we either take our Root node as part of our diameter, or Not. Hence Diameter of the tree = maximum ( dp[root][0] , dp[src][1]).
Lets consider node 1 as root, hence,

D = max( dp[1][0], dp[1][1])

So the total number of areas covered in this longest path is D+1.

Therefore, if (D+1) is even, answer is Yes, else No.

Setter's Solution 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define elif else if
#define pb push_back
#define pf push_front
#define MAX 400001

using namespace std;
 
string s;
int t;
 
vector<ll> adj[MAX];
ll downpath[MAX];
 
void pre(ll src, ll par){ 	//Function to pre-calculate downpath.
	
	ll maxDown=0;
	bool leaf=0;
	
	for(auto child:adj[src]){
		if(child!=par){
			pre(child,src);
			maxDown = max(maxDown, downpath[child]);
		}
	}
	if(leaf){
		downpath[src]=0;
	}
	else{
		downpath[src]=1+maxDown;
	}
}
 
ll dp[MAX][2];
 
void dfs(ll src, ll par){
	
	dp[src][0]=dp[src][1]=0;
	
	bool leaf=true;
	
	for(auto child:adj[src]){
		if(child!=par){
			leaf=false;
			dfs(child,src);
		}
	}
	if(leaf) return;
	
	for(auto child:adj[src]){
		if(child!=par){
			dp[src][0]=max(dp[src][0],max(dp[child][0],dp[child][1]));
		}
	}
	
	vector<ll> downs;
	for(auto child:adj[src]){
		if(child!=par){
			downs.pb(downpath[child]);
		}
	}
	sort(downs.begin(),downs.end(),greater<>());
	
	if(downs.size()==1){
		dp[src][1]+=downs[0];
	}
	else{
		dp[src][1] += (downs[0]+downs[1]);
	}
	
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin >> n;
    for(int i=1; i<n; i++){
    	ll a,b;
    	cin >> a >> b;
    	adj[a].pb(b);adj[b].pb(a);
	}
	pre(1,0);
	dfs(1,0);
	int ans;
	ans = 1+max(dp[1][0],dp[1][1]); 
	if(ans%2){
		cout <<"No";
	}
	else{
		cout <<"Yes";
	}
}
2

problem link ?

4

Update: (Simpler Solution implementation)

Implementation 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define elif else if
#define pb push_back
#define pf push_front
#define PI 3.1415926535897932384
#define MOD 1000000007
#define MAX 500001
using namespace std;
string s;
int t;

vector<ll> adj[MAX];

ll maxNode;
ll maxx = 0;

void dfs(ll src, ll par, ll d){
	if(d>maxx){
		maxx=d;
		maxNode=src;
	}
	for(auto child:adj[src]){
		if(child!=par){
			dfs(child,src,d+1);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ll n;
    cin >> n;
    for(ll i=0; i<n-1; i++){
    	ll a,b;
    	cin >> a >> b;
    	adj[a].pb(b);
    	adj[b].pb(a);
	}
	
	dfs(1,0,1);
	dfs(maxNode,0,1);
	
	if(maxx&1){
		cout <<"No";
	}
	else{
		cout <<"Yes";
	}
	
}
1 Like