插排树

NC17474. 插排树

描述

一年一度的山东省oi夏令营又开始了，每到这个季节，山东的oier们都会欢聚这里，一起学（tuí）习（feì）。当然，为了能更加愉快地学（tuí）习（feì），就少不了要自带电脑，用电便开始成了一种问题，于是便有一种神奇的数据结构诞生了！这就是山东省oi专用数据结构——插排树（如图）

小K为了能更好的学（tuí）习（feì），所以他想尽量的往后做，所以现在请你帮帮他，他最远可以离讲台多远。

已知插排树的根节点在讲台上，有且仅有一个根节点（根节点入度为0），最远距离即所有插排的长度，小K电脑线的长度忽略不计

本题良心大样例下载地址： https://kench.co/tree.zip

输入描述

第一行一个整数n表示有n个节点
然后n-1行，每行三个整数a,b,c，表示插排a是接在插排b上的，插排a的长度为c

输出描述

一个整数n表示最远距离

示例1

输入:

输出:

说明:

1=>3=>7=>9

上次编辑到这里，代码来自缓存点击恢复默认模板

C(clang11) 解法, 执行用时: 15ms, 内存消耗: 380K, 提交时间: 2021-02-10 21:17:34

#include<stdio.h>
#include<math.h>
int main()
{
    int n,t,s[100001];
    scanf("%d",&n);
    while(n--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        s[a] = s[b]+c;
        t=fmax(t,s[a]);
    }
    printf("%d",t);
    return 0;
}

Python(2.7.3) 解法, 执行用时: 125ms, 内存消耗: 11588K, 提交时间: 2018-08-10 20:19:43

import sys
n = int(sys.stdin.readline())
l = []
for _ in range(n-1):
    l.append([int(x) for x in sys.stdin.readline().split()])
d = [0] * (n + 1)
for a, b, c in l:
    d[a] = d[b] + c
print sorted(d)[-1]

C++11(clang++ 3.9) 解法, 执行用时: 42ms, 内存消耗: 732K, 提交时间: 2018-08-11 17:56:39

#include<bits/stdc++.h>
using namespace std;int n,a,b,c,i,M=0,s[50050];int main(){cin>>n;for(i=1;i<n;i++)cin>>a>>b>>c,s[a]=s[b]+c,M=max(M,s[i]);cout<<M;}