problem link:https://usaco.org/index.php?page=viewproblem2&cpid=1520
I am doing an approach where I go over all the paths from the root node(I reversed the tree so its from root p_i to i), and check if the courage +1th maximum is <= skill.
#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin("inp.in");
ofstream fout("inp.out");
int n;
vector<vector<int>> adj(2e5+1);
vector<bool> vis(2e5+1);
map<pair<int,int>,int> enj,dif;
map<int,vector<pair<int,int>>> courage;
void dfs(int node, int totEnj, set<int> &totDif){
if(vis[node]){
return;
}
vis[node]=true;
int max1=0,max2=0,max3=0,max4=0,max5=0,max6=0,max7=0,max8=0,max9=0,max10=0,max11=0;
//courage 0 corresponds to max1, 1 to max2, 2 to max3, ... 10 to max11
//for each courage store the {max,totEnj}
int cnt=1;
for(auto it = totDif.rbegin() ; it!=totDif.rend() && cnt!=12; it++){
if(cnt==1){max1=*it;}
if(cnt==2){max2=*it;}
if(cnt==3){max3=*it;}
if(cnt==4){max4=*it;}
if(cnt==5){max5=*it;}
if(cnt==6){max6=*it;}
if(cnt==7){max7=*it;}
if(cnt==8){max8=*it;}
if(cnt==9){max9=*it;}
if(cnt==10){max10=*it;}
if(cnt==11){max11=*it;}
cnt++;
}
courage[0].push_back({max1,totEnj});
courage[1].push_back({max2,totEnj});
courage[2].push_back({max3,totEnj});
courage[3].push_back({max4,totEnj});
courage[4].push_back({max5,totEnj});
courage[5].push_back({max6,totEnj});
courage[6].push_back({max7,totEnj});
courage[7].push_back({max8,totEnj});
courage[8].push_back({max9,totEnj});
courage[9].push_back({max10,totEnj});
courage[10].push_back({max11,totEnj});
for(auto it : adj[node]){
totDif.insert(dif[{node,it}]);
dfs(it,totEnj+enj[{node,it}],totDif);
totDif.erase(dif[{node,it}]);
}
}
signed main(){
fin >> n;
for(int i=2 ; i <= n ; i++){
int p,d,e; fin >> p >> d >> e;
adj[p].push_back(i);
dif[{p,i}]=d;
enj[{p,i}]=e;
}
set<int> r;
dfs(1,0,r);
for (int i=0 ; i<=10 ; i++) {
sort(courage[i].rbegin(),courage[i].rend());
vector<pair<int,int>> replace;
//make strictly decreasing
int minA=courage[i][0].first,minB=courage[i][0].second;
replace.push_back({minA,minB});
for (int j=1 ; j < courage[i].size() ; j++) {
if (courage[i][j].first<minA && courage[i][j].second<minB) {
minA=courage[i][j].first;
minB=courage[i][j].second;
replace.push_back({minA,minB});
}
}
sort(replace.begin(),replace.end());
courage[i]=replace;
}
int m; fin >> m ;
while (m--) {
int sI,cI; fin >> sI>> cI;
//TTTTTFFF, get last T. true when sI>=courage[i][j].first, assign idx of last T and ret courage[i][idx].second
int low=0,high=courage[cI].size()-1;
int ans=-1;
while (low<=high) {
int mid=low+(high-low)/2;
if (sI>=courage[cI][mid].first) {
ans=max(ans,mid);
low=mid+1;
} else {
high=mid-1;
}
}
if (ans==-1) {
fout << 0 << endl;
continue;
}
fout << courage[cI][ans].second << endl;
}
}```