P5021 [NOIP 2018 提高組] 賽道修建

題意簡述

給定一棵含 $n$ 個點的無向帶權樹，求將其分裂為 $m$ 條鏈后，最短的一條鏈的最大長度是多少？

點可以重復使用，邊不可以重復使用。

思路

二分答案貪心判定貌似可以？

看一下數據規模。

$a_i=1$ ，菊花圖。鏈最多含兩條邊。

$b_i=a_i+1$ ，整棵樹是一條鏈。

分支不超過 $3$ ？感覺在有意引導。是二叉樹。

菊花圖是最有用的，考慮菊花圖時如何求解。設當前二分出的賽道長度為 $mid$ ：

顯然此時一條鏈最多含兩條邊，考慮按邊權排序：

1**.已經大于 $mid$ 的邊**不必再拼接其他邊，因為它已經能產生貢獻了，再與其他邊拼接，自身貢獻不變的同時，阻止了其他邊產生貢獻的可能，必然不優。

2.剩下的邊里，從小到大，對于每個邊 $x$ ，二分（減小查詢復雜度）查詢出與它拼接能產生長度大于 $mid$ 的最短的一條邊，即找到最小的 $y$ ，滿足 $x+y\ge mid$ 。

為什么？如果用更長的邊（ $>y$ ），那么可能會使得原本可以產生貢獻的 $y$ 被拋棄，又因為自身不夠長而無法再次與別的邊產生貢獻，相反，被使用的更長邊顯然更有可能與別的邊拼接產生貢獻，因此選擇最小的 $y$ 即可。

菊花圖的情況已經可以求解。不妨把每一個子樹視作上述菊花圖的情況，現在子樹內已經得到最優解，如何向父節點擴展？

由于每個結點到父節點的邊是唯一的，那么只能選擇一條邊傳遞給父節點，供后續產生貢獻，那么，不難想到傳遞 剩余未匹配邊 中最長的一條。因為最長，后續產生貢獻的概率越大，緩解了父節點的匹配壓力，保證了全局最優解。可以用 $dp[u]$ 表示當前結點最長未匹配邊，到父節點出只需將父節點的邊權加上 $dp[u]$ 即可。

當子樹求解完成時，與子節點相連的邊指向哪里已經不再重要，只需記錄并排序邊權即可，用 $multiset$ 。

代碼實現

其實細節很多：

1.C++11 及以上： erase 返回刪除指定元素后下一個有效迭代器。

2.在 $multiset$ 中查找到第一個大于等于 $y$ 的元素時一定要判斷，有可能就是自己，如果未判斷就刪除會引起各種奇怪錯誤。

3. 我因為 $res=m$ 放在 $dfs$ 后，調了半天全輸出 $0$。

#include <bits/stdc++.h>using namespace std;const int N = 5e4 + 100;
int n,m,L = INT_MAX,R,res,ans; 
bool vis[N];
struct Edges{int v,w;
};
vector <Edges> gra[N];void read(int &res){int x = 0,w = 1;char ch = 0;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = (x << 3) + (x << 1) + (ch - '0');ch = getchar();}res = x * w;
}bool cmp(Edges a,Edges b){return a.w < b.w;
}int dfs(int u,int limit){vis[u] = true;//記錄與子樹相連的邊 int cnt = 0;multiset <int> match;//優先在子樹內求解for(auto edge : gra[u]){int v = edge.v;//連接父親的邊跳過 if(vis[v]) continue;match.insert(edge.w + dfs(v,limit));} //在當前子樹匹配//長度已經滿足的 for(auto it = match.begin();it != match.end();)if(*it >= limit){it = match.erase(it);res--;  }else{it++;}
//	需要兩兩匹配的for(auto it = match.begin();it != match.end();){int y = limit - (*it);auto _it = match.lower_bound(y);if(_it == match.end() || _it == it){it++;continue; } res--;match.erase(_it);it = match.erase(it);} if(match.empty()) return 0;return *match.rbegin();
}void solve(){int l = L,r = R,mid;while(l <= r){mid = l + r >> 1;memset(vis,false,sizeof(vis));res = m;dfs(1,mid);if(res <= 0){l = mid + 1;ans = mid;}else r = mid - 1;	}printf("%d\n",ans);
} int main(){read(n);read(m);int u,v,w;for(int i = 1;i < n;i++){read(u);read(v);read(w);gra[u].push_back({v,w});gra[v].push_back({u,w});L = min(L,w);R += w;}//二分答案solve(); return 0;
}

挺好的一道樹上二分+貪心。