C(clang 3.9) 解法, 执行用时: 124ms, 内存消耗: 6360K, 提交时间: 2019-06-09 16:24:00

#include <stdio.h>
#define max(a,b) ((a)>(b))?(a):(b)
int N=0,waste[200011]={0},time[200011]={0},of[200011]={1},g[200011]={0};
int main(){
    int n,a,b,c;
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        scanf("%d",&waste[i]);
    }
    for(int i=2;i<=n;i++){
        scanf("%d %d %d",&a,&b,&c);
        g[a]=1;
        time[b]=c;
        of[b]=a;
    }
    for(int i=2;i<=n;i++){
        if(g[i]==1) continue;
        int t=of[i];
        while (t!=1){
            time[i]+=time[t];
            t=of[t];
        }
        time[i]+=waste[i];
        N=max(N,time[i]);
    }
    printf("%d",N);
    return 0;
}

Python3 解法, 执行用时: 928ms, 内存消耗: 55140K, 提交时间: 2021-09-07 11:05:40

n = int(input().strip())
understanding_time = list(map(int, input().strip().split(' ')))

pass_time = {}
for i in range(n):
    pass_time[i + 1] = {}
for i in range(n - 1):
    temp_cin = list(map(int, input().strip().split(' ')))
    pass_time[temp_cin[0]][temp_cin[1]] = temp_cin[2]

def get_depth(person):
    if not pass_time[person]:
        return understanding_time[person - 2]
    else:
        memo_time = []
        for i in pass_time[person]:
            memo_time.append(get_depth(i) + pass_time[person][i])
        return max(memo_time)

print(get_depth(1))

C++14(g++5.4) 解法, 执行用时: 193ms, 内存消耗: 12380K, 提交时间: 2019-06-08 21:55:28

#include <bits/stdc++.h>
using namespace std;

int a[200005];
int maxx = 0;
vector<pair<int,int>> G[200005];
void dfs(int nowx, int nowt = 0)
{
    maxx = max(nowt + a[nowx], maxx);
    for (auto & v: G[nowx])
        dfs(v.first, nowt + v.second);
}
int main()
{
    int n;
    scanf("%d",&n);
    for (int i = 2; i <= n; i++) scanf("%d",&a[i]);
    for (int i = 1; i < n; i++)
    {
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        G[u].emplace_back(v,c);
    }
    dfs(1);
    printf("%d\n",maxx);
    return 0;
}

C++ 解法, 执行用时: 252ms, 内存消耗: 8736K, 提交时间: 2021-06-15 15:08:23

#include<bits/stdc++.h>
using namespace std;
int a[200010];
vector<pair<int,int> >g[200020];
int ma=0;
void dfs(int x,int temp){
    int i;
    ma=max(ma,a[x]+temp);
    for(i=0;i<g[x].size();i++){
        dfs(g[x][i].first,temp+g[x][i].second);
    }
}
int main(){
    int n,i;
    cin>>n;
    for(i=2;i<=n;i++)cin>>a[i];
    for(i=2;i<=n;i++){
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back({y,z});
    }
    dfs(1,0);
    cout<<ma;
}