ABC369G As far as possible
Tag：贪心、长链剖分
题目描述
给定一个 \(N\) 个结点的带边权的树， 记边权为 \(L_i\)。
对于所有的 \(K \in [1,N]\) 求解如下问题：
首先青木会在树上指定 \(K\) 个点， 之后高桥选择一条起点与终点都在 \(1\) 号点的路径， 要求经过所有青木选择的点。
定义分数为高桥路径的长度，高桥想最小化分数，青木想最大化分数。
数据说明：
- \(2\leq N\leq 2\times 10^5\)
- \(1\leq L_i\leq 10^9\)
分析
首先分析题目，我们会发现在 \(K\) 个点被指定了之后， 这里有一个比较显然的结论， 青木能选择的最优解其实是固定的， 无论树的结构与点的选择如何， 一定存在一种构造方案使得得分是 \(1\) 号点到所有的被选点路径上的边权的两倍。 因此我们只需要考虑如何选择 \(K\) 个点就可以了。
不难发现这里存在一种十分显然的贪心， 第一次选的结点一定是深度最深的一个点， 之后的每一次都去选择一条最长的路径， 不难想到选择最长的路径一定是选择某个叶子结点。 如此反复直到所有的叶子都被选过了， 这个时候再选择点就不会对得分造成贡献了。
比较显然，上述过程的本质是一个长链剖分， 我们对树进行长链剖分之后每次贪心地选择一条最长链， 对于得分的贡献就是最长链长度的两倍， 直到把所有链都选择完之后， 后续的所有选择都无法有贡献。
除此之外，本题只是用到了长链剖分的思路， 实际代码实现的时候不必实现一个长链剖分。
代码实现
void NeverSayNever() {
int n; cin >> n;
vector<vector<PII>> adj(n+1);
for (int i = 1; i < n ; ++i) {
int u,v,w; cin >> u >> v >> w;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
vector<int> chains;
auto dfs = [&](auto &&self,int cur,int fa)->int{
int res = 0;
for(auto &[nxt,w] : adj[cur]){
if(nxt == fa) continue;
int son = self(self,nxt,cur);
if(son + w > res){
chains.push_back(res);
res = son + w;
}else{
chains.push_back(son + w);
}
}
return res;
};
chains.push_back(dfs(dfs,1,0));
std::sort(chains.begin(), chains.end(),[&](int x,int y){
return x > y;
});
int ans = 0;
for (int i = 0; i < n ; ++i) {
if(i < chains.size()){
ans += chains[i] * 2;
}
cout << ans << endl;
}
}
日志
本页面创建于 2024/09/11 09:25