Code with Cisco | 2024 | Hard Tree Problem | Online Assessment | Desi QnA | Kumar K | Set - 40

Question

Answer 1

Code for it -

 

int getMinServers(int n, vector<int> f, vector<int> t, vector<int> w, vector<int>v) {
using ll=long long;
vector<ll>sz(n),mx(n);
vector<vector<array<ll,2>>>a(n);
for(ll i=0;i<f.size();i++){
    f[i]--;
    t[i]--;
    a[f[i]].push_back({t[i],w[i]});
    a[t[i]].push_back({f[i],w[i]});
     
}
ll ans=0;
function<void(ll,ll)>dfs1=[&](ll u, ll p){
  sz[u]=1;
  for(auto[v,w]:a[u])  if(v!=p){
      mx[v]=max(mx[u]+w,w);
      dfs1(v,u);
      sz[u]+=sz[v];
  }
};
function<void(ll,ll)>dfs2=[&](ll u, ll p){
    if(u!=0 && mx[u]>v[u]) ans+=sz[u];
    else{
        for(auto [v,w]:a[u]) if(v!=p){
            dfs2(v,u);
        }
            }
};
dfs1(0,-1);
dfs2(0,-1);
return ans;
}

Answer 2

Good quality pics -