题目
分析
本题一看就是DP的基本思路，关键点之一是处理好数据结构。按照题意，一个节点\(u\)可以连到若干个节点\(v_i\)，且相应的权重为\(w_i\)。可以用如下代码声明：
vector<vector<pair<int, int>>> adj(n + 1);其中，pair<int, int>表示(v, w)对；对于一个节点u而言，可以有很多这样的对，所以是vector<pair<...>>，而最后有很多u，所以再套一层vector，并初始化其容量为n+1。
算法核心是，对于某个节点u来说，到达某点v的开销是节点u的开销加上u-v的权重：dp[v] = dp + (ll)w;，由于我们要找开销最大的路径，所以这个dp[v]需要不断更新为最大值。
答案
思考
初始状态时，所有节点的开销都设置为-INF，表示无法到达，这也是后续判定能否构成1-n的关键。而另一个特殊情况是只有一个节点，但我们一开始就设置dp[1]=1，所以不用特别处理。