【题解】dia和尊严

根据题目给出的条件，

一个人可以有多个下属，但一个人最多只能有一个上级。

可以得出其实是一棵树。我们要求的其实就是从根节点到每一个节点的代价，这个代价是根节点到这个节点的边权加上这个节点的点权。
所以只需要进行一次dfs，dfs的过程中记录边权，然后计算每个点的代价的时候加上这个点的点权就可以了。

#include<iostream>
#include<vector>
using namespace std;

const int MAXN = 2e5+10;
int a[MAXN];
vector<pair<int,int> > G[MAXN];
int ans;
void dfs(int now,int sum)
{
    ans = max(ans,a[now]+sum);
    for(int i = 0 ; i < G[now].size() ; i ++)
    {
        dfs(G[now][i].first,sum+G[now][i].second);
    }
}
int main()
{
    int n;
    cin >> n;
    for(int i = 2 ; i <= n ; i++){cin >>a[i];}
    for(int i = 1 ; i < n ; i++)
    {
        int x,y,k;
        cin >> x>>y>>k;
        G[x].push_back(make_pair(y,k));
    }
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}