- 如果你是在统计答案时才剪去每个点对它子节点贡献的影响,那么把每个点的贡献值排序时cmp函数不要写成
bool cmp(pair<int,int> x,pair<int,int> y){
if(x.first!=y.first) return x.first>y.first;
else return son[x.second]<son[y.second];
}
要写成
bool cmp(pair<int,int> x,pair<int,int> y){
return x.first-son[x.second]>y.first-son[y.second];
}
因为每个点到根节点的距离并非这个点的真实贡献,再减掉每个点对它子节点贡献的影响值才是它对答案的真正贡献。
可能大多数人在排序前就已经减掉了这个吧
- 检查你的数组大小,是 2e5,不是 1e5。
- 不开 long long 见祖宗