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]的值为0
    dfs(1,0);
    dfs2(1,0);
    cout<<maxx<<endl;
}