[心之碎片][0622] - 树网的核

柿子饼同学

树网的核 link
1 遍过
4 h


知识点
单调队列


思路
直径的性质: 到一个点的最远距离的点在直径上, 偏心距只会在直径两个端点和不在直径上的路径上产生答案
###1
先找出直径, 记下来, 对于每个直径上的点求出这个点不过直径所能走到最远的点的距离, 记作 val
然后在直径上跑单调队列, 对于一条路径 , 它的偏心距就是 max(路径中val的最大值, 直径两端点到路径端点的最大值)
###2
可以简单一些, 只求出 max(一个点不过直径的最远距离)
根据直径的性质可知 , 当路径不包含这个最大值的点时, 路径端点到直径端点的答案更大
当包含时, 可以让路径端点到直径端点和这个取 max 即可
O(n)


需要进步的地方
代码太长, 加了一些不必要的数组, 要精简代码
一开始写的时候没想清楚, 浪费了时间
整体想不出来, 可以想想单个点是怎么算答案的, 对思考有帮助
先想想一个操作影响的范围, 不要一直想着 memset 0
II 方法很好, 求直径之后沿着 f 数组跳上去即可, 不用截下来或打标记
写 II 的时候 dfs 忘记递归了...


最终代码

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 5e5 + 5;
   
5. typedef long long ll;
   
6. 
   
7. struct Edge{
   
8.     int v, w;
   
9. };
   
10. 
    
11. int n;
    
12. ll s;
    
13. vector<Edge> e[N];
    
14. 
    
15. // f 父节点, d 到根的距离
    
16. int p, q, f[N];
    
17. ll d[N];
    
18. 
    
19. void dfs1(int u, int pa, int & id){
    
20.     for(auto ed : e[u]){
    
21.         if(ed.v == pa) continue;
    
22.         f[ed.v] = u;
    
23.         d[ed.v] = d[u] + ed.w;
    
24. 
    
25.         if(d[ed.v] > d[0]){
    
26.             d[0] = d[ed.v];
    
27.             id = ed.v;
    
28.         }
    
29. 
    
30.         dfs1(ed.v, u, id);
    
31.     }
    
32. }
    
33. 
    
34. void Work(){
    
35.     f[1] = 0, d[1] = 0;
    
36.     dfs1(1, 0, p); // 直径一端点是 p
    
37.     f[p] = 0, d[p] = 0, d[0] = 0;
    
38.     dfs1(p, 0, q); // 直径顺序: p -> q
    
39.     // 不需要 memset, 后续计算不会算到直径
    
40. }
    
41. 
    
42. // 求不过直径的最大距离
    
43. ll mxd = 0;
    
44. 
    
45. void dfs2(int u, int f){
    
46.     for(auto ed : e[u]){
    
47.         if(ed.v == f) continue;
    
48.         d[ed.v] = d[u] + ed.w;
    
49.         if(d[ed.v] > mxd) mxd = d[ed.v];
    
50.         dfs2(ed.v, u);
    
51.     }
    
52. }
    
53. 
    
54. int main(){
    
55.     ios::sync_with_stdio(0);
    
56.     cin.tie(0);
    
57. 
    
58.     cin >> n >> s;
    
59.     for(int i = 1; i < n; i++){
    
60.         int x, y, z;
    
61.         cin >> x >> y >> z;
    
62.         e[x].push_back({y, z});
    
63.         e[y].push_back({x, z});
    
64.     }
    
65. 
    
66.     Work();
    
67.    
    
68.     // 求 mxd
    
69.     // j 是 i 的上一个节点
    
70.     for(int i = q, j = 0; i; j = i, i = f[i]){
    
71.         for(auto ed : e[i]){
    
72.             if(ed.v == f[i] || ed.v == j) continue;
    
73. 
    
74.             // 现在只有不在直径上的点了
    
75.             d[ed.v] = ed.w;
    
76.             mxd = max(mxd, d[ed.v]);
    
77.             dfs2(ed.v, i);
    
78.         }
    
79.     }
    
80. 
    
81.     // 尺取路径 [i, j]
    
82.     ll ans = 2e18;
    
83.     for(int i = q, j = q; i; i = f[i]){
    
84.         while(f[j] != f[i] && d[j] - d[i] > s) j = f[j];
    
85.         ans = min(ans, max({mxd, d[i], d[q] - d[j]}));
    
86.     }
    
87. 
    
88.     cout << ans;
    
89. 
    
90.     return 0;
    
91. }

复制代码

一开始的代码

1. /*
   
2. 找直径, 标记, 取下直径
   
3. 每个点求一个不在直径上的侧边最远点距离
   
4. 每个点的权值 max(最远点距, 直径两端点到点的距离)
   
5. 单调队列跑直径, 求最大值最小
   
6. */
   
7. 
   
8. #include <bits/stdc++.h>
   
9. using namespace std;
   
10. 
    
11. typedef long long ll;
    
12. 
    
13. const int N = 5e5 + 5;
    
14. 
    
15. struct Edge{
    
16.     int v, w;
    
17. };
    
18. 
    
19. vector<Edge> e[N];
    
20. int n;
    
21. ll m;
    
22. 
    
23. // 找最远点
    
24. bitset<N> vis;
    
25. int f[N];
    
26. ll maxd, id;
    
27. ll dist[N];
    
28. int d[N], cnt;
    
29. 
    
30. void dfs(int u, int pa, ll dis){
    
31.     f[u] = pa;
    
32.     if(dis > maxd){
    
33.         maxd = dis;
    
34.         id = u;
    
35.     }
    
36. 
    
37.     for(auto ed : e[u]){
    
38.         if(ed.v == pa || vis[ed.v]) continue;
    
39.         dfs(ed.v, u, dis + ed.w);
    
40.     }
    
41. }
    
42. 
    
43. // 求直径, 扒下来
    
44. void Getd(){
    
45.     dfs(1, 0, 0);
    
46.     memset(f, 0, sizeof(f));
    
47.     maxd = 0;
    
48.     int rt = id;
    
49.     dfs(rt, 0, 0);
    
50.     maxd = 0;
    
51.    
    
52.     while(id != rt){
    
53.         d[++cnt] = id;
    
54.         vis[id] = 1;
    
55. 
    
56.         for(auto ed : e[id]){
    
57.             if(ed.v == f[id]){
    
58.                 dist[cnt] = ed.w;
    
59.                 break;
    
60.             }
    
61.         }
    
62.         id = f[id];
    
63.     }
    
64.     vis[rt] = 1;
    
65.     d[++cnt] = rt;
    
66.     for(int i = cnt - 1; i >= 1; i--) dist[i] += dist[i + 1];
    
67. }
    
68. 
    
69. // 求权值
    
70. ll val[N];
    
71. 
    
72. void Getval(){
    
73.     for(int i = 1; i <= cnt; i++){
    
74.         dfs(d[i], f[d[i]], 0);
    
75.         val[i] = maxd;
    
76.         maxd = 0;
    
77.     }
    
78. }
    
79. 
    
80. int q[N], l = 1, r = 0;
    
81. 
    
82. int main(){
    
83.     ios::sync_with_stdio(0);
    
84.     cin.tie(0);
    
85. 
    
86.     cin >> n >> m;
    
87.     for(int i = 1; i < n; i++){
    
88.         int x, y, z;
    
89.         cin >> x >> y >> z;
    
90.         e[x].push_back({y, z});
    
91.         e[y].push_back({x, z});
    
92.     }
    
93. 
    
94.     Getd();
    
95.     Getval();
    
96. 
    
97.     int last = 1;
    
98.     ll ans = LONG_LONG_MAX;
    
99. 
    
100.     for(int i = 1; i <= cnt; i++){
     
101.         while(r >= l && val[q[r]] <= val[i]) r--;
     
102.         while(last <= i && dist[last] - dist[i] > m) last++;
     
103.         q[++r] = i;
     
104.         while(l <= r && q[l] < last) l++;
     
105. 
     
106.         ans = min(ans, max({dist[1] - dist[last], dist[i], val[q[l]]}));
     
107.     }
     
108. 
     
109.     cout << ans;
     
110. 
     
111.     return 0;
     
112. }

复制代码

FishC

嘿！看起来你在处理一个关于树结构（特别是树的直径和核）的编程问题。让我帮你解读一下这个有点复杂的思路，顺便加点幽默感来让它更容易理解。

### 问题背景：
我们有一个树形结构，树的节点数为 `n`。目标是找出树的“核”，即使得某种距离最小化的特殊点。

### 核心概念解释：
1. **树的直径**：这是树中最长路径的长度。比如说你有一棵大树，从根到最远的叶子走了一圈，那这根最长的树干就是直径。
2. **单调队列**：一种数据结构，用来快速找到某个范围内的最大值或者最小值。就像是去超市购物，你是排在队伍里等着付款，单调队列就有点像你在观察谁最快结账，然后你立刻换队伍。

### 解决思路：
1. **先找到树的直径**。
   - 随意选一个起点，跑一次深度优先搜索（DFS），找出最远的节点（叫它 `p`）。
   - 然后以 `p` 为起点，再跑一次DFS，找到另一个最远的节点（叫它 `q`）。这样我们就有了树的直径。

2. **计算不过直径的最大距离**：
   - 对于直径上的每个节点，找出从它出发到不在直径上的节点的最远距离。这个距离记作 `val`。

3. **使用单调队列优化**：
   - 在直径上用单调队列找出每段路径的偏心距（即路径中所有节点的最大 `val` 值）。

### 代码讲解：
下面是你给出的代码的简化注释版本：

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. #include <cstring>
   
5. 
   
6. using namespace std;
   
7. 
   
8. const int N = 5e5+5;
   
9. typedef long long ll;
   
10. 
    
11. struct Edge {
    
12.     int v, w;
    
13. };
    
14. 
    
15. int n;
    
16. ll s;
    
17. vector<Edge> e[N];
    
18. int p, q, f[N];
    
19. ll d[N];
    
20. 
    
21. void dfs1(int u, int pa, int &id, ll dis) {
    
22.     if (dis > d[id]) {
    
23.         id = u;
    
24.         d[id] = dis;
    
25.     }
    
26.     for (auto &ed : e[u]) {
    
27.         if (ed.v == pa) continue;
    
28.         dfs1(ed.v, u, id, dis + ed.w);
    
29.     }
    
30. }
    
31. 
    
32. void findDiameter() {
    
33.     memset(d, 0, sizeof(d));
    
34.     p = 1; dfs1(p, 0, p, 0); // 找到直径的一端 p
    
35.     memset(d, 0, sizeof(d));
    
36.     dfs1(p, 0, q, 0); // 找到直径的另一端 q
    
37. }
    
38. 
    
39. ll max_dist_not_in_diameter;
    
40. 
    
41. void dfs2(int u, int pa, ll dist) {
    
42.     max_dist_not_in_diameter = max(max_dist_not_in_diameter, dist);
    
43.     for (auto &ed : e[u]) {
    
44.         if (ed.v == pa) continue;
    
45.         dfs2(ed.v, u, dist + ed.w);
    
46.     }
    
47. }
    
48. 
    
49. int main() {
    
50.     ios::sync_with_stdio(false);
    
51.     cin.tie(0);
    
52. 
    
53.     cin >> n >> s;
    
54.     for (int i = 1; i < n; i++) {
    
55.         int x, y, z;
    
56.         cin >> x >> y >> z;
    
57.         e[x].push_back({y, z});
    
58.         e[y].push_back({x, z});
    
59.     }
    
60. 
    
61.     // Step 1: Find the diameter
    
62.     findDiameter();
    
63.    
    
64.     // Step 2: Calculate max distance not in diameter
    
65.     max_dist_not_in_diameter = 0;
    
66.     for (int i = 1; i <= n; ++i) {
    
67.         if (d[i] == 0) { // means node i is not on the diameter
    
68.             dfs2(i, 0, 0);
    
69.         }
    
70.     }
    
71. 
    
72.     // Step 3: Traverse diameter and use sliding window (or monotone deque) to find minimum value
    
73.     ll ans = LLONG_MAX;
    
74.     for (int i = q, j = q; i; i = f[i]) {
    
75.         while (f[j] != f[q] && d[i] - d[j] > s) j = f[j];
    
76.         ans = min(ans, max({max_dist_not_in_diameter, d[i], d[q] - d[j]}));
    
77.     }
    
78. 
    
79.     cout << ans << endl;
    
80.     return 0;
    
81. }

复制代码

### 笑话时间：
想象一下，树的直径就像你每天上学的最长那条公交路线，保证无论多早起床，这条路总是最长的。而树的核呢，就像是你在公交车站等车的时候，发现哪里人少，能最快上车的地方。希望这种比喻能让你的编程之路不再那么枯燥，加油！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

某一个“天”

kiara_03

好

harryhan123

6

hhy2024

听懂掌声

简柠啦

很不错

thekfjie

心之碎片太好了

希儿的

我目前不懂，但
不影响我大为震撼

harryhan123

harryhan123