[心之碎片][0622] - 巡逻

柿子饼同学

巡逻 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 的值
证明取直径最优 :

调整法 分两种情况讨论：

一：若选的第一个环与直径无相交的边，则第二个环选直径最优，这等价于第一个环选直径。

二：若选的第一个环与直径有相交的边，将直径与第二个环相交但不与第一个环相交的部分加到第一个环上，答案不变，然后再在第一个环上加上直径上不与第二个环重叠的点，答案增加，因此不如第一个环就直接选直径。

综上，第一个环选直径一定不劣。

代码

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 1e5 + 5;
   
5. 
   
6. int n, k, ans;
   
7. vector<int> e[N];
   
8. int p, q, f[N], d[N];
   
9. bitset<N> isd;
   
10. 
    
11. void dfs(int u, int pa, int & id){
    
12.     for(auto ed : e[u]){
    
13.         if(ed == pa) continue;
    
14.         f[ed] = u;
    
15.         if(isd[u] && isd[ed]) d[ed] = d[u] - 1;
    
16.         else d[ed] = d[u] + 1;
    
17. 
    
18.         if(d[0] <= d[ed]){
    
19.             d[0] = d[ed];
    
20.             id = ed;
    
21.         }
    
22. 
    
23.         dfs(ed, u, id);
    
24.     }   
    
25. }
    
26. 
    
27. void Getd1(){
    
28.     d[0] = 0, f[1] = 0, d[1] = 0;
    
29.     dfs(1, 0, p);
    
30.     d[0] = 0, d[p] = 0, f[p] = 0;
    
31.     dfs(p, 0, q);
    
32. }
    
33. 
    
34. int dp[N], res;
    
35. void Getd2(int u, int f){
    
36.     for(auto ed : e[u]){
    
37.         if(ed == f) continue;
    
38.         int w = 1;
    
39.         if(isd[ed] && isd[u]) w = -1;
    
40.         Getd2(ed, u);
    
41.         res = max(res, dp[u] + dp[ed] + w);
    
42.         dp[u] = max(dp[u], dp[ed] + w);
    
43.     }
    
44. }
    
45. 
    
46. int main(){
    
47.     ios::sync_with_stdio(0);
    
48.     cin.tie(0);
    
49. 
    
50.     cin >> n >> k;
    
51.     for(int i = 1; i < n; i++){
    
52.         int x, y;
    
53.         cin >> x >> y;
    
54.         e[x].emplace_back(y);
    
55.         e[y].emplace_back(x);
    
56.     }
    
57. 
    
58.     ans = 2*(n - 1);
    
59.     if(k == 0){
    
60.         cout << ans;
    
61.         return 0;
    
62.     }
    
63. 
    
64.     Getd1();   
    
65.     ans -= d[0] - 1;
    
66.     if(k == 1){
    
67.         cout << ans;
    
68.         return 0;
    
69.     }
    
70. 
    
71.     for(int i = q; i; i = f[i]){
    
72.         isd[i] = 1;
    
73.     }
    
74.     Getd2(1, 0);
    
75.     ans -= res - 1;
    
76.     cout << ans;
    
77. 
    
78.     return 0;
    
79. }

复制代码

harryhan123

啊