傳送門

題意：給一棵帶邊權(quán)的樹，求$M$條沒(méi)有公共邊的路徑的最小長(zhǎng)度的最大值。

$N\le 50000$

拋開NOIP不談，其實(shí)這題本身出的很好

顯然二分

問(wèn)題轉(zhuǎn)化成了“最多可以找多少條長(zhǎng)度不小于$k$的路徑”

遞歸處理

對(duì)于每個(gè)結(jié)點(diǎn)$i$，先統(tǒng)計(jì)它的子樹剩下的鏈加上當(dāng)前邊權(quán)。

現(xiàn)在我們得到了若干個(gè)數(shù)，表示以$i$為頂?shù)倪€沒(méi)用過(guò)的鏈的長(zhǎng)度

我們希望用這些數(shù)湊出$k$

大于等于$k$的可以直接統(tǒng)計(jì)答案

有如下貪心策略：從小到大二分最小的可以匹配的，最后把不能匹配的最長(zhǎng)的作為剩下的鏈傳回去

為什么？

首先，很顯然盡量匹配小的

如果我們留了一條很長(zhǎng)的鏈不匹配而要傳上去，也最多產(chǎn)生$1$的貢獻(xiàn)。而現(xiàn)在直接匹配也會(huì)有$1$的貢獻(xiàn)，不配白不配。

為什么從小到大？

如果我們從大到小，或者用一些神奇的順序，那就是出現(xiàn)大配小的情況。從小到大我們就算不匹配盡量小也能重現(xiàn)之前的狀態(tài)，盡量小就肯定更優(yōu)了。

用multiset維護(hù)即可。

細(xì)節(jié)有點(diǎn)多。注意大于等于$k$的必須在開始彈掉，否則可能浪費(fèi)一個(gè)小的。

菊花圖可能卡常，可以跑個(gè)直徑作為二分上限。

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <set> #define MAXN 50005 #define MAXM 100005 using namespace std; struct edge{int u,v,w;}e[MAXM]; int head[MAXN],nxt[MAXM],cnt; void addnode(int u,int v,int w) {e[++cnt]=(edge){u,v,w};nxt[cnt]=head[u];head[u]=cnt; } int dp[MAXN]; int count(int u,int f,int k) {multiset<int> s;int ans=0;for (int i=head[u];i;i=nxt[i])if (e[i].v!=f){ans+=count(e[i].v,u,k);if (dp[e[i].v]+e[i].w>=k) ++ans;else s.insert(dp[e[i].v]+e[i].w);}while (!s.empty()){int mn=*s.begin();multiset<int>::iterator p=s.lower_bound(k-mn);if (p==s.begin()) ++p;if (p==s.end()){dp[u]=max(dp[u],mn);s.erase(s.begin());continue;}++ans;s.erase(p);s.erase(s.begin());}return ans; } int dis[MAXN]; void dfs(int u,int f) {for (int i=head[u];i;i=nxt[i])if (e[i].v!=f){dis[e[i].v]=dis[u]+e[i].w;dfs(e[i].v,u);} } int main() {int n,m;scanf("%d%d",&n,&m);for (int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);addnode(u,v,w);addnode(v,u,w);}dfs(1,0);int mx=0;for (int i=1;i<=n;i++) if (dis[i]>dis[mx]) mx=i;dis[mx]=0;dfs(mx,0);int l=0,r=0,mid;for (int i=1;i<=n;i++) r=max(r,dis[i]);while (l<r){mid=(l+r+1)>>1;memset(dp,0,sizeof(dp));if (count(1,0,mid)>=m) l=mid;else r=mid-1;}printf("%d\n",l);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【NOIP2018】赛道修建【二分】【树形dp】【multiset】【贪心】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。