INOI2001 - Editorial

PROBLEM LINK:

Practice

DIFFICULTY:

Simple

PREREQUISITES:

Depth first search

PROBLEM:

There’s a company with a tree hierarchy consisting of some departments. Every employee, except the department heads, has a manager. A department is called Type Even if its size is even - Type Odd if its size is odd. The department head of a Type Even department is the employee with the smallest ID, while for Type Odd departments it’s the employee with the greatest ID. We want to find the sum of the levels of employees in Type Even departments and same for Type Odd, where the level of an employee means how many people have command on him in the tree hierarchy, plus one.

QUICK EXPLANATION:

For every department, you’ll dfs starting from any employee to find its type, the employee with the smallest number, and the employee with the greatest number. That tells you which employee is the department head. Then, you’ll do another dfs starting from the department head, carrying the level of the current employee as a parameter, and summing up as you go down the tree.

EXPLANATION:

For every pair of employees in the input, we know they work together in the same department, but we need to determine that department’s head to get the full image of the tree hierarchy.

Let’s focus on one department. We can do a depth first search starting from any employee in this department to know its size, and hence its type. Recall that if it’s Type Even, the department’s head is the employee with the smallest ID, while if it’s Type Odd, it’s the employee with the greatest ID. We can do another depth first search to get that employee, or even better, we can just modify our original depth first search to get us the employees with the smallest and greatest IDs. And then depending on the department’s type, its head will either be the former or the latter.

Now that we have the department’s head, we can easily calculate the levels of all the employees. Let’s go down the tree with another depth first search, carrying with us the level of the current employee as a parameter. Whenever we descend down into a new employee, the level just increases by one, because we add one more manager. We should simply add up the levels to the answer as we go down the tree. Of course, we’ll have 2 separate variable for Type Even and Type Odd departments.

To solve it for all the departments, you should just iterate over the employees, and whenever you meet an employee for the first time, they have to be in a new department, so you’ll run the above algorithm starting from that employee.

SOLUTIONS:

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
bool vis[100005];
vector<int> v[100005];
pair<int,pair<int,int> > get(int node,int p) //it returns the type of the department, the minimum employee number, and the maximum employee number respectively
{
	vis[node]=1;
	pair<int,pair<int,int> > ret({1,{node,node}});
	for (int u:v[node])
	{
		if (u!=p)
		{
			auto tmp=get(u,node);
			ret.first^=tmp.first;
			ret.second.first=min(ret.second.first,tmp.second.first);
			ret.second.second=max(ret.second.second,tmp.second.second);
		}
	}
	return ret;
}
long long dfs(int node,int p,int l) //the parameters are the employee number, its manager, and its level (the number of managers above him) .. it calculates the department's score
{
	long long ret=l;
	for (int u:v[node])
	{
		if (u!=p)
		ret+=dfs(u,node,l+1);
	}
	return ret;
}
int main()
{
	int t;
	scanf("%d",&t);
	while (t--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for (int i=1;i<=n;i++)
		{
			vis[i]=0;
			v[i].clear();
		}
		while (m--)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			v[a].push_back(b);
			v[b].push_back(a);
		}
		long long e=0,o=0;
		for (int i=1;i<=n;i++)
		{
			if (!vis[i]) //this is a new department
			{
				auto p=get(i,0);
				if (p.first) //Type Odd department
				o+=dfs(p.second.second,0,1);
				else //Type Even department
				e+=dfs(p.second.first,0,1);
			}
		}
		printf("%lld %lld\n",e,o);
	}
}