来写篇题解捞人。
这题貌似数据范围小炸了,导致各种最短路横生...
但是我们完全可以不用最短路。
因为我们知道这个东西的结构是树!直接来一发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; }