解析

它還真的不難。
樂。

這題沒做出來有些諤諤。
外層wqs二分顯而易見，里面不知道為啥我總覺得這個題可以貪心。
然后一直試圖在原樹直徑上下功夫，一籌莫展。
看到題解“dp”兩個字這題也就做完了…
就相當于要把一棵樹分成若干條無交鏈，每分條需要一定代價，最大化價值和。
記錄以下每個點向兒子連幾條邊以及是否和父親連邊之類的即可。
（pair用于wqs二分的dp是真香）

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") using namespace std;const int N=6e5+100; const ll inf=3e11;inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m,k;struct node{int to,nxt,w; }p[N<<1]; int fi[N],cnt; inline void addline(int x,int y,int w){p[++cnt]=(node){y,fi[x],w};fi[x]=cnt; } #define pr pair<ll,ll> #define mkp make_pair pr operator + (pr a,pr b){return mkp(a.first+b.first,a.second+b.second);} pr operator + (pr a,ll b){return mkp(a.first+b,a.second);} pr dp[3][N]; ll w; void dfs(int x,int fa){dp[0][x]=mkp(0,0);dp[1][x]=dp[2][x]=mkp(-inf,0);for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==fa) continue;dfs(to,x);dp[2][x]=max(dp[2][x],max(dp[2][x]+dp[0][to],(dp[1][x]+dp[1][to])+p[i].w));dp[1][x]=max(dp[1][x],max(dp[1][x]+dp[0][to],(dp[0][x]+dp[1][to])+p[i].w));dp[0][x]=max(dp[0][x],dp[0][x]+dp[0][to]);}dp[1][x]=max(dp[1][x],dp[0][x]);dp[0][x]=max(dp[0][x],mkp(dp[0][x].first+w,dp[0][x].second+1));dp[0][x]=max(dp[0][x],mkp(dp[1][x].first+w,dp[1][x].second+1));dp[0][x]=max(dp[0][x],mkp(dp[2][x].first+w,dp[2][x].second+1));return; }signed main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifmemset(fi,-1,sizeof(fi));cnt=-1;n=read();m=read()+1;for(int i=1;i<n;i++){int x=read(),y=read(),w=read();addline(x,y,w);addline(y,x,w);}ll st=-inf,ed=inf;while(st<ed){ll mid=(st+ed)>>1;w=mid;dfs(1,0);if(dp[0][1].second>=m) ed=mid;else st=mid+1;}w=st;debug("w=%lld\n",w);dfs(1,0);printf("%lld\n",dp[0][1].first-m*w);return 0; }

總結

以上是生活随笔為你收集整理的P4383 [八省联考 2018] 林克卡特树（wqs二分、树形dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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