警示后人:如果你 WA ON#5 or #9 or RE ON#7
查看原帖
警示后人:如果你 WA ON#5 or #9 or RE ON#7
777756
UFOI楼主2023/8/1 11:12
  1. 如果你是在统计答案时才剪去每个点对它子节点贡献的影响,那么把每个点的贡献值排序时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];
}

因为每个点到根节点的距离并非这个点的真实贡献,再减掉每个点对它子节点贡献的影响值才是它对答案的真正贡献。

可能大多数人在排序前就已经减掉了这个吧

  1. 检查你的数组大小,是 2e5,不是 1e5。
  2. 不开 long long 见祖宗
2023/8/1 11:12
加载中...