F. The Chocolate Spree

Chocolate Spree"/>

F. The Chocolate Spree

题意：求树上两条不相交链的最大权值和。

分析：显然求一条链是简单的：定义：

dp1[u]：以u为根的子树中一端为u的最长单链

dp2[u]：以u为根的子树中最长的交叉链

可以写出：

dp1[u]=max(dp1[u],dp1[v]+a[u]);
dp2[u]=max(dp2[u],dp2[v]);
dp2[u]=max(dp2[u],最长dp1[u]+次长dp1[u]-a[u]);

然后我们考虑最暴力的枚举边让树分成两棵子树分别求最大链，这样换根的时候我们需要对每个点维护3条最长链和2条最长交叉链。这里学习了一下使用set暴力维护若干个最大值的写法，不再需要手写if else了。然后我们加上几句话就可以写出2022ccpc桂林G了。

代码：
 

int a[maxn];
vector<int>e[maxn];
int sz[maxn];
multiset<int>dp1[maxn],dp2[maxn];//以u为根的子树中 一端为u的最长单链/最长的交叉链
int pass[maxn];void md(multiset<int>&s)//使dp1/dp2始终有5个最优选择
{if(s.size()>5) s.erase(s.begin());else if(s.size()<5) s.insert(0);
}void dfs(int u,int fa)
{for(int i=1;i<=5;i++) md(dp1[u]),md(dp2[u]);sz[u]=1;for(auto v:e[u]){if(v==fa) continue;dfs(v,u);sz[u]+=sz[v];auto it1=--dp1[v].end(),it2=--dp2[v].end();dp1[u].insert(*it1+a[u]); md(dp1[u]);dp2[u].insert(*it2); md(dp2[u]);}if(sz[u]==1){dp1[u].insert(a[u]); md(dp1[u]);dp2[u].insert(a[u]); md(dp2[u]);}else{auto it1=--dp1[u].end(),it2=it1;--it2;pass[u]=*it1+*it2-((*it2)?a[u]:0);dp2[u].insert(pass[u]); md(dp2[u]);}
}   int maxx;void dfs2(int u,int fa)//对于每条边将树分成两棵子树，分别统计子树最大交叉链
{if(dp2[u].find(pass[u])!=dp2[u].end())//删去经过根节点的交叉链并更新最大值{dp2[u].erase(dp2[u].find(pass[u])); md(dp2[u]);maxx=max(maxx,pass[u]);}for(auto v:e[u]){if(v==fa) continue;int v1=*(--dp1[v].end())+a[u];if(dp1[u].find(v1)!=dp1[u].end()) dp1[u].erase(dp1[u].find(v1)),md(dp1[u]);int v2=*(--dp2[v].end());if(dp2[u].find(v2)!=dp2[u].end()) dp2[u].erase(dp2[u].find(v2)),md(dp2[u]);auto it1=--dp1[u].end(),it2=it1;it2--;int nowv=*(--dp2[v].end()),nowu=max(*(--dp2[u].end()),*it1+*it2-((*it2)?a[u]:0));maxx=max(maxx,nowv+nowu);dp1[v].insert(*it1+a[v]); md(dp1[v]);dp2[v].insert(nowu); md(dp2[v]);dfs2(v,u);dp1[u].insert(v1), md(dp1[u]);dp2[u].insert(v2), md(dp2[u]);}
}void solve()
{int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}e[1].push_back(n+1);//防止根节点的度为1，否则换根时dp1[1]的值为0dfs(1,0);dfs2(1,0);cout<<maxx<<endl;
}