FINDWAYS - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Bhupat Jangid
Tester: Dheeraj Bhagchandani
Editorialist: Bhupat Jangid

DIFFICULTY:

MEDIUM

PREREQUISITES:

Tree,DFS

PROBLEM:

NOOB is in bizarre habit of counting everything. So one day he decided to count number of ways in which he can visit a very popular miraculous city Chefland. Chefland is a rooted tree consisting of n vertices with the root at vertex 1. Vertex 1 is also the only entrance in Chefland and every leaf vertex contains an exit door. But there is a problem. Some of the vertices are poisonous. If he visits consecutive m poisonous vertices he will eventually die, otherwise he succussfully visits that city. NOOB feels some difficulties solving this problem and needs your in finding number of possible ways?

EXPLANATION:

we have to choose a node and then run DFS on it in such a way that it can’t traverse consecutive m poisonous nodes and count number of leaf nodes which is traversable.
For example in given test case we choose node 1 as root node and run DFS on it then we can traverse at most two leaf nodes which are 6 and 7.

Capture
Capture1058×533 23.1 KB

in given diagram if node become red then we will backtrack and traverse remaining all nodes and count leaf node which is marked in green.

SOLUTIONS:

Setter's Solution 
n,m = map(int,input().split())
lst = list(map(int,input().split()))
adj=[]
for i in range(n):
    adj.append([])
cnt=0
temp=0
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    adj[a].append(b)
    adj[b].append(a)
arr = [[0,0,0]]
while len(arr):
    t,temp,prev = arr.pop()
    if lst[t] == 1:
        temp += 1
    else:
        temp = 0
    if temp >= m: 
        continue
    if len(adj[t]) == 1 and t != 0:
        cnt += 1
        continue
    for i in adj[t]:
        if i == prev: 
            continue
        arr.append((i,temp,t))
    
print(cnt)
Tester's Solution 
#include <bits/stdc++.h>
using namespace std; 
#define pb push_back
#define ll long long
#define M 1000000007
#define MM 998244353
#define fr first
#define sc second
#define vc vector
#define pii pair<int,int>
#define psi pair<string,int>
int a[100005],vis[100005];
int c=0,m;
vector<int> v[100005];

void dfs(int z,int r){
    vis[z]=1;

    int t=(a[z]==0)?0:(r+1);
    int isleaf=0;
    // check if continues 
    if(t>=m)return;
    for(int i=0;i<v[z].size();i++){
        if(vis[v[z][i]])continue;
        isleaf++;
        dfs(v[z][i],t);
    }
    if(isleaf == 0)c++;
}
int main(){
    ios_base::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    dfs(1,0);
    cout<<c;
}
2 Likes