题解 | #悬崖#

E.筑巢

树形dp板子(实际是dfsQAQ)

我实际上是写复杂了只需要1维的树形dp t[now][1]可以用ans = max(ans,t[now][0])替代

t[now][0]以now为根的子树最大舒适度(包含now) t[now][1]以now为根的子树最大舒适度(不包含now)

设son为now的某个子树,若t[now][0]+(now和son边的舒适度)对t[now][0]为正收益则加上,如果是负收益就不加 t[now][0],t[now][1]初始化为a[now](以单结点为联通块的舒适度

t[now][1] = max(t[now][0],t[son][1],t[now][1])//要么直接从子树转移,要么从当前结点转移

最后记得开long long

code:

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>;
#define int long long
//t[i][0]表示以加上根结点的联通块
int t[100005][2];
int a[100005];
vector<pair<int,int>> edge[100005];
int n;
void dfs(int now,int fa)
{
    t[now][0] = a[now];//初始化为
    t[now][1] = a[now];
    for(int i = 0;i<edge[now].size();++i)
    {
        if(edge[now][i].first==fa) continue;
        dfs(edge[now][i].first,now);
        t[now][0] = max(t[now][0]+t[edge[now][i].first][0]+edge[now][i].second,t[now][0]);
        t[now][1] = max(t[edge[now][i].first][1],max(t[now][1],t[now][0]));
    }
}
signed main()
{
    cin>>n;
    for(int i = 1;i<=n;++i)
        cin>>a[i];
    for(int i = 1;i<n;++i)
    {
        int x,y,z;
        cin>>x>>y>>z;
        edge[x].push_back(make_pair(y,z));
        edge[y].push_back(make_pair(x,z));
    }
    dfs(1,0);
    cout<<t[1][1]<<endl;
    return 0;
}