当前位置:   article > 正文

CF1120D Power Tree

cf power tree

题目传送门

Description

给定一棵有根树,可以用wx的代价控制x点,控制后可以给该点子树里的叶子同时加上一个数。求最小代价,使得叶子上为任何不同的数,你都可以把它们变为0n105

Solution

首先将叶子结点按照dfs序排序,为一个序列。

控制一个点后加上一个数的操作相当于区间加,可以考虑在差分数组上操作。

将所有叶子结点变为0,相当于将差分数组变为0。若x对应区间[l,r],那么wx可以修改序列上lr+1的值。将所有值都变为0,需要可以修改的位置连接起来,即形成一棵树。于是将每个店的(l,r+1)建一条边,跑一边最小生成树即可。

Code

  1. #include<cstdio>
  2. #include<vector>
  3. #include<algorithm>
  4. #define pb push_back
  5. #define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
  6. #define per(i, a, b) for (register int i=(a); i>=(b); --i)
  7. using namespace std;
  8. inline void chkmax(int &x, int y){x<y?(x=y):0;}
  9. inline void chkmin(int &x, int y){x>y?(x=y):0;}
  10. const int N=200005;
  11. struct node{int x, y, w, id;}E[N];
  12. bool operator < (node a, node b){return a.w<b.w;}
  13. int L[N], R[N], deg[N], fa[N], ans[N], val[N], sum, cnt;
  14. vector<int> G[N];
  15. long long res;
  16. inline int read()
  17. {
  18. int x=0,f=1;char ch=getchar();
  19. for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
  20. for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
  21. return x*f;
  22. }
  23. void dfs(int u, int fa)
  24. {
  25. if (deg[u]==1 && u>1) L[u]=R[u]=++cnt;
  26. for (int v: G[u]) if (v^fa)
  27. {
  28. dfs(v, u);
  29. chkmin(L[u], L[v]);
  30. chkmax(R[u], R[v]);
  31. }
  32. E[u]=(node){L[u], R[u]+1, val[u], u};
  33. }
  34. int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
  35. int main()
  36. {
  37. int n=read();
  38. rep(i, 1, n) val[i]=read(), L[i]=n;
  39. rep(i, 1, n-1)
  40. {
  41. int u=read(), v=read();
  42. G[u].pb(v); G[v].pb(u);
  43. deg[u]++; deg[v]++;
  44. }
  45. dfs(1, 0);
  46. sort(E+1, E+n+1);
  47. rep(i, 1, cnt+1) fa[i]=i;
  48. for (int l=1, r=1; l<=n; l=r+1, r++)
  49. {
  50. while (E[r].w==E[r+1].w && r<n) r++;
  51. rep(i, l, r)
  52. {
  53. int fx=find(E[i].x), fy=find(E[i].y);
  54. if (fx^fy) sum++, ans[E[i].id]=1;
  55. }
  56. rep(i, l, r)
  57. {
  58. int fx=find(E[i].x), fy=find(E[i].y);
  59. if (fx^fy) fa[fx]=fy, res+=(long long)E[i].w;
  60. }
  61. }
  62. printf("%lld %d\n", res, sum);
  63. rep(i, 1, n) if (ans[i]) printf("%d ", i);
  64. return 0;
  65. }

转载于:https://www.cnblogs.com/ACMSN/p/10674399.html

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/64667
推荐阅读
相关标签
  

闽ICP备14008679号