[心之碎片][0622] - 巡逻
本帖最后由 柿子饼同学 于 2024-6-22 19:30 编辑巡逻 link
提交 4 次
3 h
知识点
dp求树的直径 贪心
思路
K == 0, ans0 = 2*(n - 1)
K == 1, 取直径1, ans1 = ans0 - 直径1 + 1
K == 2, 直径上的边权变成 -1, 再算直径2, ans2 = ans1 - 直径2 + 1
这里取反边权是因为, 第二条边如果覆盖了直径, 路程反而会增加这一段的, 别的路径不碍事
求直径就相当于求让路径可以尽可能减小的路程
O(n)
注意点
dfs 不能处理负权树求直径 , 只能用 dp 求, 写的时候 dp 写反了 , 要注意是用 ed 求出 u 的值
证明取直径最优 :
调整法 分两种情况讨论：一：若选的第一个环与直径无相交的边，则第二个环选直径最优，这等价于第一个环选直径。二：若选的第一个环与直径有相交的边，将直径与第二个环相交但不与第一个环相交的部分加到第一个环上，答案不变，然后再在第一个环上加上直径上不与第二个环重叠的点，答案增加，因此不如第一个环就直接选直径。综上，第一个环选直径一定不劣。
代码#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, k, ans;
vector<int> e;
int p, q, f, d;
bitset<N> isd;
void dfs(int u, int pa, int & id){
for(auto ed : e){
if(ed == pa) continue;
f = u;
if(isd && isd) d = d - 1;
else d = d + 1;
if(d <= d){
d = d;
id = ed;
}
dfs(ed, u, id);
}
}
void Getd1(){
d = 0, f = 0, d = 0;
dfs(1, 0, p);
d = 0, d = 0, f = 0;
dfs(p, 0, q);
}
int dp, res;
void Getd2(int u, int f){
for(auto ed : e){
if(ed == f) continue;
int w = 1;
if(isd && isd) w = -1;
Getd2(ed, u);
res = max(res, dp + dp + w);
dp = max(dp, dp + w);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for(int i = 1; i < n; i++){
int x, y;
cin >> x >> y;
e.emplace_back(y);
e.emplace_back(x);
}
ans = 2*(n - 1);
if(k == 0){
cout << ans;
return 0;
}
Getd1();
ans -= d - 1;
if(k == 1){
cout << ans;
return 0;
}
for(int i = q; i; i = f){
isd = 1;
}
Getd2(1, 0);
ans -= res - 1;
cout << ans;
return 0;
}
啊
页:
[1]