題干：

鏈接：https://ac.nowcoder.com/acm/contest/157/D
來源：牛客網

一年一度的山東省oi夏令營又開始了，每到這個季節，山東的oier們都會歡聚這里，一起學（tuí）習（feì）。當然，為了能更加愉快地學（tuí）習（feì），就少不了要自帶電腦，用電便開始成了一種問題，于是便有一種神奇的數據結構誕生了！這就是山東省oi專用數據結構——插排樹（如圖）

小K為了能更好的學（tuí）習（feì），所以他想盡量的往后做，所以現在請你幫幫他，他最遠可以離講臺多遠。

已知插排樹的根節點在講臺上，有且僅有一個根節點（根節點入度為0），最遠距離即所有插排的長度，小K電腦線的長度忽略不計

輸入描述:

第一行一個整數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<50000c小于20a,b小于等于n

解題報告：

? ?這題數據水了，相當于保證了輸入順序了。所以你直接讀入的時候處理就可以了。但是其實應該記錄下每個點的入度，然后去跑dfs的。

? 兩種dfs方法，要么按照一般dp的方式，先dfs，再dp[cur]=max(dp[cur],dp[v]);，最后直接輸出dp[root]。

? 要么用遍歷的方式，，到了每個點，先dis[v]=dis[cur]+邊權，再dfs，最后On掃一遍dis數組。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int n; vector<int> vv; int dis[MAX]; int main() {cin>>n;for(int a,b,c,i = 1; i<=n-1; i++) {cin>>a>>b>>c;dis[a] = dis[b] + c;}int ans = 0;for(int i = 1; i<=n; i++) ans = max(ans,dis[i]);cout <<ans;return 0 ; }

?

總結

以上是生活随笔為你收集整理的【牛客 - 157D】插排树（dfs，树形dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。