KAZOKU - Editorial

PROBLEM LINK:

Practice
Contest

Author: Nihal Mittal

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Greedy, Graph, DFS

PROBLEM:

The problem asks us to first calculate the sum of subtree of all nodes and then tell the minimum difference between any 2 nodes.

QUICK EXPLANATION:

We can first calculate the sum of subtree of all nodes using dfs traversal technique and store them in an array. Then we sort the array and update the answer as ans = min(ans, a[i] - a[i-1]).

EXPLANATION:

We are given a tree of N nodes. Firstly, we have to calculate the sum of the subtree for all nodes. We will denote this array by Na. For the first subtask all nodes except root node 1 have the sum of subtree equal to its corresponding array value.
Node 1 will have the sum of subtree for all N-1 leaf values .
Na[1] = A[1] +.. A[n], 1 <= n<= N
Na[2..N] = A[2..N]

For the second subtask We can simply construct a different array as its a path graph with root 1 as beginning node. For the third subtask we can use dfs traversal technique to efficiently construct sum of subtree array. All the leaf nodes have the sum of subtree value equal to its corresponding value in the given array. Now if we are given a subtree like - 1->2->3 and we want to calculate the sum of subtree of Node 1 we have to calculate the sum of subtree for Node 2 and 3 first. Since Node 3 is a leaf node its value will be equal to its corresponding array value. Sum of subtree for Node 2 will be A[2] + Na[3] and similarly for Node 3 it will be
A[1] + Na[2] + Na[3].

Now we have an array N which consists of sum of subtree for all nodes. We will sort this array as the difference between adjacent array elements will be minimized. We will traverse this array and finally update the answer if we obtain a smaller difference between adjacent elements.

TIME COMPLEXITY

Time complexity is O(NlogN) where N is the number of nodes.

SOLUTION:

Setter's Solution
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mk make_pair
#define pb push_back
#define in insert
#define se second
#define fi first
#define mod 1000000007
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define all(v) (v).begin(),(v).end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define pii pair<ll,ll>
#define vi(x) vector<x>
#define maxn 100005
using namespace std;
ll n;
vector<ll> v[100005];
vector<ll> a(100005) , sub, visited(100005) , si(100005);
 
void dfs(ll so)
{
	visited[so] = true;
    si[so] = a[so];
	for(auto u: v[so])
	{
		if(!visited[u])
		{
			dfs(u);
			si[so] += si[u];
		}
	}
}
signed main()
{
    fast;
   
    ll i,ans = LLONG_MAX;
    cin>>n;
    for(i=0;i<n-1;i++)
    {
    	ll x,y;
    	cin>>x>>y;
    	v[x].pb(y);
    	v[y].pb(x);
    }
    for(i=1;i<=n;i++) cin>>a[i];
    dfs(1);
    for(i=1;i<=n;i++)
    {
    	sub.pb(si[i]);
    }
    sort(all(sub));
    for(i=1;i<n;i++) ans = min(ans , sub[i] - sub[i-1]);
    cout<<ans;
} 

Very well explain. :wink:

1 Like