admin 管理员组文章数量: 1086019
蔬菜
题目描述
您正站在森林中最显眼的一棵树前，一条叫 Skqliao 的人正在树上打盹，他告诉您这棵树是一棵无根树，在第 i 个点上有 x 颗蔬菜，如果您想要回去的话就需要收集尽量多的蔬菜。当然乐于助人的 Skqliao 也会帮助您。具体来讲，首先你和 Skqliao 各选择一个不同的起点，接着轮流选定一个与自己相邻的且两人都未经过的点并到达该点。当某人无法移动时，另一人可以继续移动，直到两人都无法移动为止。当你或 Skqliao 经过某点时就可以收集该点所有蔬菜，请你制定合理策略 (包括 Skqliao 选择的初始位置和操作方式) 尝试获得最多的蔬菜。
题解
大力分讨，显然拎出来一个点，要么是在这个点的子树内，要么是树外再连进来，各种撞车情况分讨一下即可
代码
#include <bits/stdc++.h>
#define maxn 200005
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
int read(){int res,f=1; char c;while(!isdigit(c=getchar())) if(c=='-') f=-1; res=(c^48);while(isdigit(c=getchar())) res=(res<<3)+(res<<1)+(c^48);return res*f;
}
struct EDGE{int u,v,nxt;
}e[maxn<<1];
int cnt,head[maxn];
void add(int u,int v){e[++cnt]=(EDGE){u,v,head[u]}; head[u]=cnt;}
int n,w[maxn];
LL ans,dn1[maxn],dnn1[maxn],dn2[maxn],dnn2[maxn],dn3[maxn],s1[maxn],sn1[maxn],s2[maxn],sn2[maxn],up[maxn];
void DFS_1(int u,int far){for(int i=head[u];~i;i=e[i].nxt){int v=e[i].v; if(v==far) continue;DFS_1(v,u);if(dn1[v]+w[v]>=dn1[u]){dn3[u]=dn2[u];dn2[u]=dn1[u]; dnn2[u]=dnn1[u];dn1[u]=dn1[v]+w[v]; dnn1[u]=v;}else if(dn1[v]+w[v]>=dn2[u]){dn3[u]=dn2[u];dn2[u]=dn1[v]+w[v]; dnn2[u]=v;}else if(dn1[v]+w[v]>=dn3[u]){dn3[u]=dn1[v]+w[v];}LL tmp=max(s1[v],dn1[v]+dn2[v]+w[v]);if(tmp>=s1[u]){s2[u]=s1[u]; sn2[u]=sn1[u];s1[u]=tmp; sn1[u]=v;}else if(tmp>=s2[u]){s2[u]=tmp; sn2[u]=v;}}
}
void DFS_2(int u,int far){for(int i=head[u];~i;i=e[i].nxt){int v=e[i].v; if(v==far) continue;up[v]=up[u]+w[u];if(dnn1[u]!=v) up[v]=max(up[v],dn1[u]+w[u]);else up[v]=max(up[v],dn2[u]+w[u]);DFS_2(v,u); }
}
int main(){memset(head,-1,sizeof head);n=read();for(int i=1;i<=n;i++) w[i]=read();for(int i=1,u,v;i<n;i++){u=read(); v=read();add(u,v); add(v,u);}DFS_1(1,0); DFS_2(1,0);for(int i=1;i<=n;i++){//cout<<" "<<i<<" "<<dn1[i]<<" "<<dn2[i]<<" "<<dn3[i]<<" "<<s1[i]<<" "<<s2[i]<<" "<<up[i]<<endl;ans=max(ans,s1[i]+s2[i]); ans=max(ans,up[i]+dn1[i]+dn2[i]+w[i]);if(sn1[i]!=dnn1[i]){if(sn1[i]!=dnn2[i]) ans=max(ans,s1[i]+dn1[i]+max(up[i],dn2[i])+w[i]);else{ans=max(ans,s1[i]+dn1[i]+max(up[i],dn3[i])+w[i]);if(sn2[i]!=dnn1[i]) ans=max(ans,s2[i]+dn1[i]+max(up[i],dn2[i])+w[i]);else ans=max(ans,s2[i]+dn2[i]+max(up[i],dn3[i])+w[i]);}}else{ans=max(ans,s1[i]+dn2[i]+max(up[i],dn3[i])+w[i]);if(sn2[i]!=dnn2[i]) ans=max(ans,s2[i]+dn1[i]+max(up[i],dn2[i])+w[i]);else ans=max(ans,s2[i]+dn1[i]+max(up[i],dn3[i])+w[i]);}}printf("%lld\n",ans);return 0;
}
本文标签： 蔬菜
版权声明：本文标题：蔬菜 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/b/1686921354a47750.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论