題目鏈接：點擊查看

題目大意：給出一棵樹，每個點都有權值，現在要求輸出樹上權值和最大的一條鏈

題目分析：讀完題后第一反應是樹的直徑，趕緊去找來模板貼上，交上去WA了一發后意識到，正常樹的直徑只能處理非負邊權，而這個題目中有負權，然后就想用樹形dp亂搞試試，但奈何我的dp非常弱，搞到最后也沒搞出來，比賽時我想的是dp[ i ]代表的是從葉子結點到點 i 為止最大的權值和，一路向上轉移，交上去一直WA，賽后看了別人的代碼意識到，這樣的dp無法處理以點 i 為中間過渡點的子鏈，再后來才知道，這是一個樹的直徑處理負權的模板題，就當長見識了吧，貼上模板直接過了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;vector<int>node[N];LL dp[N],a[N],ans;void dfs(int u,int fa) {dp[u]=a[u];ans=max(ans,a[u]);for(auto v:node[u]){if(v==fa)continue;dfs(v,u);ans=max(ans,dp[u]+dp[v]);dp[u]=max(dp[u],dp[v]+a[u]);} }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);ans=-inf;for(int i=1;i<=n;i++)scanf("%lld",a+i);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}dfs(1,-1);printf("%lld\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的牛客 - 树上子链(树的直径-处理负权)的全部內容，希望文章能夠幫你解決所遇到的問題。

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