牛客练习赛24D——插排树

链接：https://www.nowcoder.com/acm/contest/157/D
来源：牛客网
题目描述
一年一度的山东省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
输入
复制
9
2 1 2
3 1 2
4 1 1
5 2 3
6 2 1
7 3 1
8 3 4
9 7 5
输出
复制
8
说明
1=>3=>7=>9
备注:
对于30%的数据 n<233
对于70%的数据 n<2333
对于100%的数据 n<50000
c小于20
a,b小于等于n

题一开始没读懂，问了一下才知道就是求多叉树的最长链（起点未知）
那就直接dfs搜索一下就行了
主要是这个数据很大，因为要保存权值，一开始尝试用二维数组，但是还是太大了，所以就用vector，但是vector里得存连接的顶点和权值，因此用一个结构体

代码：

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN=5010;
struct node{
    int a;
    int c;
};
vector<node> cost[MAXN];
int dfs(int n){
    int ans=0;
    int l=cost[n].size();
    for(int i=0;i<l;i++){
        ans=max(ans,dfs(cost[n][i].a)+cost[n][i].c);
    }
    return ans;
}
int main(void){
    //freopen("data.txt","r",stdin);
    int n;
    scanf("%d",&n);
    int a,b,c;
    int Max=0;
    node t;
    for(int i=0;i<n-1;i++){
        scanf("%d%d%d",&a,&b,&c);
        t.a=a;
        t.c=c;
        cost[b].push_back(t);
        Max=max(Max,max(a,b));
    }
    int ans=0;
    for(int i=0;i<=Max;i++){
        ans=max(ans,dfs(i));
    }
    printf("%d\n",ans);
    return 0;
}