[BUG] - <title> Test case contradicts the problem description #30216
Description
LeetCode Username
aryan_lem
Problem Number, Title, and Link
https://leetcode.com/problems/minimum-increments-to-equalize-leaf-paths/
Bug Category
Incorrect test case (Output of test case is incorrect as per the problem statement)
Bug Description
You are given an integer n and an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi] indicates an edge from node ui to vi .
testcase number 554:
n =
3
edges =
[[1,0],[0,2]]
cost =
[2,1,3]
According to problem statement: it clearly state an edge going from ui to vi, if so, 1->0 and 0->2, would make 1 as the root, however 0 is supposed to be the root (mentioned in the problem).
please give insights.
Language Used for Code
C++
Code used for Submit/Run operation
class Solution {
public:
vector<int>par;
vector<vector<int>>adj;
int n;
int minIncrease(int n, vector<vector<int>>& edges, vector<int>& cost) {
n=cost.size();
par.resize(n);adj.resize(n);
for(auto it:edges){
adj[it[0]].push_back(it[1]);
par[it[1]]=it[0];
}
set<int>st;
for(int i=1;i<n;i++)if(adj[i].size()==0)st.insert(i);
long long maxi=0;
vector<long long>tot(n);tot[0]=cost[0];
queue<pair<int,int>>q;q.push({0,tot[0]});
vector<int>dep(n);
while(!q.empty()){
auto it=q.front();q.pop();
int nd=it.first,wt=it.second;
for(int cd:adj[nd]){
tot[cd]=(long long)cost[cd]+(long long)wt;
dep[cd]=dep[nd]+1;
q.push({cd,tot[cd]});
}
}
vector<int>fl(n);
for(int i=1;i<n;i++){
if(st.find(i)!=st.end()){
maxi=max(maxi,tot[i]);
fl[i]=1;
}
}
int ct=0;
for(int x:st){
// cout<<x<<": "<<tot[x]<<endl;
if(tot[x]<maxi)ct++;
}
// cout<<ct<<endl;
if(ct==0)return 0;
map<int,vector<int>>mp;
int mx=0;
for(int i=0;i<n;i++){mp[dep[i]].push_back(i);mx=max(mx,dep[i]);}
for(int i=mx-1;i>=0;i--){
for(int nd:mp[i]){
set<int>stt;
int fll=1;
for(int cd:adj[nd]){
if(fl[cd]==0){fll=0;break;}
stt.insert(tot[cd]);
}
if(fll==0)continue;
if(stt.size()==1){
int cst=*stt.begin();
if(cst<maxi){
tot[nd]=cst;
ct-=adj[nd].size();ct++;
fl[nd]=1;
}
}
}
}
return ct;
}
};Expected behavior
well, this is contradictory test case, so this testcase should not be included for judging the codes.
Screenshots
No response
Additional context
No response