CF1088F Ehab and a weird weight formula

ゞ 浴缸里的玫瑰 2021-11-13 15:38 211阅读 0赞

CF1088F Ehab and a weird weight formula

推性质猜结论题

第一步转化,考虑把点的贡献加到边里:

$con=\sum (log_2(dis(a_u,a_b))\times min(a_u,a_v))+a_u+a_v$

然后一个结论:

一个点最多有一个相邻的点比它小

因为会连出一串,只能在唯一的最小值点结束

所以,以最小值为根,建出有根树,每个点的fa就是比它小的

整个树越往祖先权值越小

不妨再给边定向,令边的方向就是:$a_u>a_v,a_u->a_v$,

每个点只会连出去一条边,所以只用最小化:$(log_2(dis(a_u,a_v))+1)\times a_v$

发现,连出的边只会是往祖先连,否则dis会更大

而log_2是上去整,所以一定是$2^k$级祖先连过去最优!

注意如果不存在$2^k$级祖先,那么和$rt$也要试着连一连

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<bits/stdc++.h>
  2. #define reg register int
  3. #define il inline
  4. #define fi first
  5. #define se second
  6. #define mk(a,b) make_pair(a,b)
  7. #define numb (ch^'0')
  8. #define pb push_back
  9. #define solid const auto &
  10. #define enter cout<<endl
  11. #define pii pair<int,int>
  12. using namespace std;
  13. typedef long long ll;
  14. template<class T>il void rd(T &x){
  15. char ch;x=0;bool fl=false;
  16. while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
  17. for(x=numb;isdigit(ch=getchar());x=x*10+numb);
  18. (fl==true)&&(x=-x);
  19. }
  20. template<class T>il void output(T x){
  21. if(x/10)output(x/10);putchar(x%10+'0');}
  22. template<class T>il void ot(T x){
  23. if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
  24. template<class T>il void prt(T a[],int st,int nd){
  25. for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
  26. namespace Miracle{
  27. const int N=5e5+5;
  28. const ll inf=0x3f3f3f3f3f3f3f3f;
  29. ll ans;
  30. int n;
  31. struct node{
  32. int nxt,to;
  33. }e[2*N];
  34. int hd[N],cnt;
  35. int a[N];
  36. void add(int x,int y){
  37. e[++cnt].nxt=hd[x];
  38. e[cnt].to=y;
  39. hd[x]=cnt;
  40. }
  41. int fa[N][20];
  42. int dfs(int x){
  43. for(reg i=hd[x];i;i=e[i].nxt){
  44. int y=e[i].to;
  45. if(y==fa[x][0]) continue;
  46. fa[y][0]=x;
  47. dfs(y);
  48. }
  49. }
  50. int main(){
  51. rd(n);
  52. int rt=0;
  53. for(reg i=1;i<=n;++i) {
  54. rd(a[i]);
  55. if(!rt||a[i]<a[rt]) rt=i;
  56. }
  57. int x,y;
  58. for(reg i=1;i<n;++i){
  59. rd(x);rd(y);add(x,y);add(y,x);
  60. }
  61. dfs(rt);
  62. for(reg j=1;j<=19;++j){
  63. for(reg i=1;i<=n;++i){
  64. fa[i][j]=fa[fa[i][j-1]][j-1];
  65. }
  66. }
  67. for(reg i=1;i<=n;++i){
  68. ll mi=inf;
  69. if(i==rt) continue;
  70. for(reg j=0;j<=19;++j){
  71. if(!fa[i][j]) {
  72. mi=min(mi,(ll)(j+1)*a[rt]);
  73. break;
  74. }
  75. mi=min(mi,(ll)(j+1)*a[fa[i][j]]);
  76. }
  77. ans+=mi+a[i];
  78. }
  79. ot(ans);
  80. return 0;
  81. }
  82. }
  83. signed main(){
  84. Miracle::main();
  85. return 0;
  86. }
  87. /*
  88. Author: *Miracle*
  89. */

转载于:https://www.cnblogs.com/Miracevin/p/10836925.html

发表评论

表情:
评论列表 (有 0 条评论,211人围观)

还没有评论,来说两句吧...

相关阅读