【题解】插排树

来写篇题解捞人。
这题貌似数据范围小炸了，导致各种最短路横生...
但是我们完全可以不用最短路。
因为我们知道这个东西的结构是树！直接来一发dp就好了啊qwq

我们用当前节点的父亲的长度+当前插排的长度就是所求的当前节点的长度。
这玩意用式子写出来就是

然后一发bfs或者dfs就搞了...
代码实现:

#include <iostream>
#include <cstdio>

using namespace std;
template <typename Tp>
inline Tp read()
{
    Tp num = 0;
    char ch = getchar(), qian;
    while (!isdigit(ch))
        qian = ch, ch = getchar();
    while (isdigit(ch))
        num = (num << 1) + (num << 3) + (ch ^ 48), ch = getchar();
    return (qian ^ '-') ? num : -num;
}
template<class Tp>
inline void read(Tp &num)
{
    num = read<Tp>();
}
struct edge
{
    int to, next;
} Edge[100086];
int cnt = 1, head[50086];
inline void add_edge(int from, int to)
{
    Edge[cnt].to = to;
    Edge[cnt].next = head[from];
    head[from] = cnt++;
}
int n, len[50086], ans;
int f[50086], In[50086];

void dfs(int n, int fa)
{
    f[n] = f[fa] + len[n];
    for (int i = head[n]; i; i = Edge[i].next)
    {
        int to = Edge[i].to;
        if (fa != to)
            dfs(to, n);
    }
}

int main()
{
    read(n);
    for (int i = 1; i < n; i++)
    {
        int f = read<int>(), t = read<int>();
        len[f] = read<int>();
        add_edge(f, t);
        add_edge(t, f);
        In[f]++;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!In[i])
            dfs(i, 0);
    }
    for (int i = 1; i <= n; i++)
    {
        ans = max(ans, f[i]);
    }
    printf("%d\n", ans);
    return 0;
}