POPPUSH5 – Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest-Link

Author: Yash Dwivedi
Tester: Shubham Kushwaha
Editorialist: Nikhil Shukla

DIFFICULTY:

MEDIUM

PREREQUISITES:

Depth first search

PROBLEM:

You are given a tree with n nodes and n-1 edges and also the information whether the edges are clean (if its weight is 1) or untidy(if its weight is 2). If the ith child is selected it cleans all the paths from i to 1(which is the root node). We have to tell the minimum number of children to be selected to clean all the paths in the tree.

QUICK EXPLANATION:

Perform dfs from the root node (1). If the current visiting node has an untidy edge connected with it check its subtree for untidy edge if yes then move ahead else choose it and increment the answer.

EXPLANATION:

This problem can be easily solved using dfs on trees performing from the root node (1). The most optimal way to choose the nodes, such that total number of children is minimum, is to choose only those nodes which have an untidy edge connected with it and its subtree has no untidy edge. It’s easy to see that if we choose a node that has an untidy edge connected with it and its subtree has another untidy edge then this won’t be optimal because the current chosen (children) node is unnecessarily cleaning the road when children in the subtree can.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(c) (c).begin(),(c).end() 
#define inf ((ll)1e18+1))
vector<ll>adj[200005];
map<pair<ll,ll>,ll>mp;
vector<ll>res;
bool dfs(ll v,ll par)
{
    bool f=false;
    for(auto i:adj[v])
    {
        if(i!=par)
        f|=dfs(i,v);
    }
    if(f)
    return true;
    if(mp.find({v,par})!=mp.end())
    {
        if(mp[{v,par}]==2)
        {
        res.push_back(v);
        return true;
        }
    }
    return false;
}
int main()
{
    int t=1;
    //cin>>t;
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    while(t--)
    {
           ll i,n;
           cin>>n;
           for(i=0;i<n-1;i++)
           {
               ll x,y,z;
               cin>>x>>y>>z;
               adj[x].push_back(y);
               adj[y].push_back(x);
               mp[{x,y}]=z;
               mp[{y,x}]=z;
               
           }
           dfs(1,-1);
           cout<<res.size()<<endl;
    }
    return 0;
}