【裸换根DP】ABC220 F - Distance Sums 2 + [USACO10MAR] Great Cow Gathering G

向右看齐 2024-03-22 11:05 99阅读 0赞

今天打算小学一手换根DP,入个门就可以!

题意:

c33561c8aa1b4774b50102052dde3efd.png

思路:

一眼换根

考虑换根DP的时候,我们考虑把以父亲作为根的贡献和以儿子作为根的贡献进行比较,用父亲推儿子

对于这道题,这样考虑贡献即可:

2eeb03175aa1465d8e8e0beae87eb311.jpeg

Code:

  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int mxn=2e5+10;
  5. const int mxe=2e5+10;
  6. struct ty{
  7. int to,next;
  8. }edge[mxe<<2];
  9. int N,u,v,tot=0;
  10. int dep[mxn],sz[mxn],dp[mxn],head[mxn];
  11. void add(int u,int v){
  12. edge[tot].to=v;
  13. edge[tot].next=head[u];
  14. head[u]=tot++;
  15. }
  16. void G_init(){
  17. tot=0;
  18. for(int i=0;i<=N;i++){
  19. head[i]=-1;
  20. }
  21. }
  22. void dfs1(int u,int fa){
  23. sz[u]=1;
  24. dep[u]=dep[fa]+1;
  25. for(int i=head[u];~i;i=edge[i].next){
  26. if(edge[i].to==fa) continue;
  27. dfs1(edge[i].to,u);
  28. sz[u]+=sz[edge[i].to];
  29. }
  30. }
  31. void dfs2(int u,int fa){
  32. for(int i=head[u];~i;i=edge[i].next){
  33. if(edge[i].to==fa) continue;
  34. dp[edge[i].to]=dp[u]+N-2*sz[edge[i].to];
  35. dfs2(edge[i].to,u);
  36. }
  37. }
  38. void solve(){
  39. cin>>N;
  40. G_init();
  41. for(int i=1;i<=N-1;i++){
  42. cin>>u>>v;
  43. add(u,v);
  44. add(v,u);
  45. }
  46. dfs1(1,0);
  47. for(int i=1;i<=N;i++) dp[1]+=dep[i];
  48. dp[1]-=N;
  49. dfs2(1,0);
  50. for(int i=1;i<=N;i++) cout<<dp[i]<<'\n';
  51. }
  52. signed main(){
  53. ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  54. int __=1;//cin>>__;
  55. while(__--)solve();return 0;
  56. }

[USACO10MAR] Great Cow Gathering G

P2986 [USACO10MAR] Great Cow Gathering G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这也是裸的换根

题意:

a7d0bd333b84495e9bf8e644555aca32.png

思路:

1e802df54da34853ae9ee19bf0f65f2b.jpeg

Code:

  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int mxn=2e5+10;
  5. const int mxe=2e5+10;
  6. struct ty{
  7. int to,next,w;
  8. }edge[mxe<<2];
  9. int N,u,v,w,tot=0,sum=0;
  10. int dep[mxn],sz[mxn],dp[mxn],head[mxn],c[mxn];
  11. void add(int u,int v,int w){
  12. edge[tot].w=w;
  13. edge[tot].to=v;
  14. edge[tot].next=head[u];
  15. head[u]=tot++;
  16. }
  17. void G_init(){
  18. tot=0;
  19. for(int i=0;i<=N;i++){
  20. head[i]=-1;
  21. }
  22. }
  23. void dfs1(int u,int fa){
  24. sz[u]=c[u];
  25. for(int i=head[u];~i;i=edge[i].next){
  26. if(edge[i].to==fa) continue;
  27. dep[edge[i].to]=dep[u]+edge[i].w;
  28. dfs1(edge[i].to,u);
  29. sz[u]+=sz[edge[i].to];
  30. }
  31. }
  32. void dfs2(int u,int fa){
  33. for(int i=head[u];~i;i=edge[i].next){
  34. if(edge[i].to==fa) continue;
  35. dp[edge[i].to]=dp[u]+(sum-2*sz[edge[i].to])*edge[i].w;
  36. dfs2(edge[i].to,u);
  37. }
  38. }
  39. void solve(){
  40. cin>>N;
  41. G_init();
  42. for(int i=1;i<=N;i++) cin>>c[i],sum+=c[i];
  43. for(int i=1;i<=N-1;i++){
  44. cin>>u>>v>>w;
  45. add(u,v,w);
  46. add(v,u,w);
  47. }
  48. dfs1(1,0);
  49. for(int i=1;i<=N;i++) dp[1]+=c[i]*dep[i];
  50. dfs2(1,0);
  51. int mi=1e18;
  52. for(int i=1;i<=N;i++) mi=min(mi,dp[i]);
  53. cout<<mi<<'\n';
  54. }
  55. signed main(){
  56. ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  57. int __=1;//cin>>__;
  58. while(__--)solve();return 0;
  59. }

发表评论

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

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

相关阅读

    相关 USACO10HOL】 Cow Politics

    题目大意 给出k组点,求出组内两点间的最大距离 核心思路 考虑贪心,每组内的最深一点一定是两最远距离点对之一。 证明很简单,可以分为在该点的祖先相同和祖先不同的