题目描述
Alice和Bob有一棵树(无根、无向)，在第i个点上有ai个巧克力。首先，两人个选择一个起点（不同的），获得点上的巧克力；接着两人轮流操作（Alice先），操作的定义是：在树上找一个两人都没选过的点并获得点上的巧克力，并且这个点要与自己上一次选的点相邻。当有一人无法操作 时，另一个人可以继续操作，直到不能操作为止。因为Alice和Bob是好朋友，所以他们希望两人得到的巧克力总和尽量大，请输出最大总和。
数据范围
对于20%的数据，n<=15
对于40%的数据，n<=100
对于60%的数据，n<=5000
对于100%的数据，n<=200000,0<=ai<=1000000000(1e9)
=w=
题目模型显然：寻找一棵树上的两条不相交的链使得权值和最大。
树形动态规划。
分两种情况讨论：
1.两条链靠近（存在一条树边，两个端点分居这两条链中）；
2.两条链分居一个结点的两颗子树。
易推。
代码
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define ll long long
using namespace std;
const char* fin="aP2.in";
const char* fout="aP2.out";
const ll inf=0x7fffffff;
const ll maxn=200007,maxm=maxn*2;
ll n,i,j,k,maxx,mxid,ans;
ll a[maxn],fi[maxn],la[maxm],ne[maxm],tot;
ll f[maxn],g[maxn],st[maxn],pre[maxn],spre[maxn],suf[maxn],ssuf[maxn];
ll Pre[maxn],Suf[maxn];
ll h[maxn],h1[maxn];
bool ban[maxn],ok[maxn];
void add_line(ll a,ll b){
tot++;
ne[tot]=fi[a];
la[tot]=b;
fi[a]=tot;
}
void xdfs(ll v,ll from){
ll i,j,k,maxx,smaxx,tmp;
st[0]=0;
for (k=fi[v];k;k=ne[k]) if (la[k]!=from) st[++st[0]]=g[la[k]];
if (from) st[++st[0]]=h1[v];
maxx=smaxx=0;
for (i=1;i<=st[0];i++){
if (maxx<st[i]){
smaxx=maxx;
maxx=st[i];
}else smaxx=max(st[i],smaxx);
pre[i]=maxx;
spre[i]=smaxx;
}
suf[st[0]+1]=ssuf[st[0]+1]=0;
maxx=smaxx=0;
for (i=st[0];i;i--){
if (maxx<st[i]){
smaxx=maxx;
maxx=st[i];
}else smaxx=max(st[i],smaxx);
suf[i]=maxx;
ssuf[i]=smaxx;
}
tmp=0;
for (k=fi[v];k;k=ne[k]) if (la[k]!=from) {
tmp++;
i=max(pre[tmp-1],suf[tmp+1]);
j=max(min(pre[tmp-1],suf[tmp+1]),max(spre[tmp-1],ssuf[tmp+1]));
h1[la[k]]=i+a[v];
h[la[k]]=a[v]+i+j;
}
for (k=fi[v];k;k=ne[k]) if (la[k]!=from) xdfs(la[k],v);
ans=max(ans,h[v]+f[v]);
}
void dfs(ll v,ll from){
ll i,j,k,maxx,smaxx,tmp;
g[v]=a[v];
for (k=fi[v];k;k=ne[k]){
if (la[k]!=from){
dfs(la[k],v);
g[v]=max(g[v],g[la[k]]+a[v]);
f[v]=max(f[v],f[la[k]]);
}
}
st[0]=0;
for (k=fi[v];k;k=ne[k]) if (la[k]!=from) st[++st[0]]=la[k];
maxx=smaxx=0;
for (i=1;i<=st[0];i++){
if (maxx<g[st[i]]){
smaxx=maxx;
maxx=g[st[i]];
}else smaxx=max(g[st[i]],smaxx);
pre[i]=maxx;
spre[i]=smaxx;
Pre[i]=max(Pre[i-1],f[st[i]]);
}
Suf[st[0]+1]=suf[st[0]+1]=ssuf[st[0]+1]=0;
maxx=smaxx=0;
for (i=st[0];i;i--){
if (maxx<g[st[i]]){
smaxx=maxx;
maxx=g[st[i]];
}else smaxx=max(g[st[i]],smaxx);
suf[i]=maxx;
ssuf[i]=smaxx;
Suf[i]=max(Suf[i+1],f[st[i]]);
}
f[v]=max(f[v],maxx+smaxx+a[v]);
tmp=0;
for (k=fi[v];k;k=ne[k])
if (la[k]!=from){
tmp++;
i=max(pre[tmp-1],suf[tmp+1]);
j=max(min(pre[tmp-1],suf[tmp+1]),max(spre[tmp-1],ssuf[tmp+1]));
ans=max(ans,f[la[k]]+i+j+a[v]);
ans=max(ans,f[la[k]]+max(Pre[tmp-1],Suf[tmp+1]));
}
}
int main(){
scanf("%lld",&n);
for (i=1;i<=n;i++) scanf("%lld",&a[i]);
for (i=1;i<n;i++){
scanf("%lld%lld",&j,&k);
add_line(j,k);
add_line(k,j);
}
dfs(1,0);
xdfs(1,0);
printf("%lld",ans);
return 0;
}=o=
求最大值和次大值，可以维护三大边。
不用像我维护什么前缀最大值，和后缀最大值= =