题目的地址：https://vjudge.net/contest/363381#problem/f
参考题解：
https://blog.csdn.net/starlet_kiss/article/details/104844691
树状数组解法
https://www.cnblogs.com/cjtcalc/p/12485536.html
dfs解法
关于这道题，就是求最小连通子图的最优解，无根
综合上述两种方法，我的代码：
//#include <bits/stdc++.h> #include <iostream> #include <cstdio> #include <string.h> #include <algorithm> using namespace std; const int maxx=200100; int edge[maxx<<1],eto[maxx<<1],head[maxx<<1]; int color[maxx],sum[maxx],ans[maxx],fu[maxx]; int tot=0,n; int read(){ /* int x=0,f=1; char s=getchar(); while(s<0||s>9){if(s=='-'){f=-f;s=getchar();}} while(s>=0&&s<=9){x=x*10+s-'0';s=getchar();} return x*f; */ char x=getchar(); while(x==' '||x=='n')x=getchar();// if(x=='0') return -1; else if(x=='1') return 1; else return 0; } void add(int u,int v){//eto到上一条以此节点为父节点的边，edge此节点的相邻结点 eto[++tot]=head[u],edge[tot]=v,head[u]=tot; } void dfs(int u,int f){ fu[u]=f; sum[u]=color[u]; for(int i=head[u];i>0;i=eto[i]){ int to=edge[i]; if(to==f)continue; dfs(to,u); if(sum[to]>0)sum[u]+=sum[to]; } } void dfs(int u,int f){ if(sum[u]>=0)ans[u]=max(sum[u],ans[f]); else if(ans[f]>0)ans[u]=ans[f]+sum[u]; else ans[u]=sum[u]; for(int i=head[u];i>0;i=eto[i]){ int to=edge[i]; if(to==f)continue; dfs(to,u); } } int main(){ scanf("%d",&n); memset(head,0,sizeof(head));//<string.h> for(int i=1;i<=n;i++){ color[i]=read(); } int a,b; for(int i=1;i<n;i++){ scanf("%d%d",&a,&b); add(a,b); add(b,a);//一条边存两次，所以需要两倍的空间 } ans[0]=sum[0]=-1*maxx; dfs(1,0); ans[1]=sum[1]; dfs(1,0); for(int i=1;i<=n;i++){printf("%d ",ans[i]);} printf("n"); return 0; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/600023.html