题目
原题链接 树网的核
题目大致意思是，找一条路径，在满足小于s的情况下，使得偏心距最小。什么是偏心距呢？偏心距指的是树网中所有点离路径距离最大的距离，我们要使最大值最小化，乍一听有点像二分。题目大致就是这个意思
题解
对于树的直径，这是一个板子题，大致思路就是随机找一个点，找到离这个点最大距离的点，然后再在这个点，继续搜索，找到距离这个点最大的点，那么这两点链接的长度即为树的直径，具体证明可以看，树的直径
这里有详细的证明，好了，我们在解决树的直径之后，那么如何求解偏心距呢？是这样的，我们以某条直径来说，通过缩小直径，根据贪心的思想，路径在不超过S的情况下，尽可能越大越好，这样到每个点的距离都会缩小。我们在讨论 如果直径上我们只选取一个点，那么距离这个点最大的一定是，我们选出直径中某一个点距离这个点最大距离的点，如果这个点距离这个点最大且不是直径上的，那么我们可以说之前找的直径有误，因为我们可以把这个点到所找的点的距离给拼接上，舍去之前找到的直径，所以假设不成立。他一定是直径上的点。我们要考虑的答案来源有两个：
我们看橙色路径 ，在满足路径长度不大于s的情况下，这个树网的直径可以是AC 也可以是AB, 我们橙色路径，首先找到直径两端到选取路径的最大值，因为前面说了可能是偏心距的来源，此外还要找直径之外的点，他们距离直径的距离可能会大于所选路径下，直径端点距离距离所选路径的距离，可能有点绕，请仔细琢磨┭┮﹏┭┮。比如说DEFG 这条路径，直径上最大的距离该路径的距离的端点是C 距离为5，但是B 距离路径长度是8 所以偏心距是8 。那我们可以怎么写呢，首先选出树的直径出来，然后在直径的某一个端点开始，运用双指针，滑动窗口，先滑窗到小于等于S 的路径 ，然后偏心距 取 直径两端点 最大距离D， ans = min(ans,D),遍历完成之后，我们枚举所有不在直径上的点距离他们离的最近的直径点的距离，如果不是离的最近的，而是经过了直径上的其他点，那么他的距离还可以缩小，答案是不对的，至此 思路大概就是这些，接下来贴上ac代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| # include<bits/stdc++.h>
using namespace std;
# define endl '\n'
const int N = 310;
vector<pair<int,int>>edges[N];
int dist[N],pre[N];
bool vis[N];
inline void dfs(int x ){
for(auto edge:edges[x]){
int y = edge.first;
int w = edge.second;
if(y!=pre[x]&&!vis[y]){
pre[y] = x;
dist[y] = dist[x] + w;
dfs(y);
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,s;
cin>>n>>s;
for(int i = 1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
edges[u].push_back({v,w});
edges[v].push_back({u,w});
}
memset(dist,0,sizeof(dist));
memset(pre,0,sizeof(pre));
pre[1] = -1;
dist[1] = 0;
int idx = 0,v = 0;
dfs(1);
for(int i = 1 ;i<=n;i++){
if(dist[i] > v){
v = dist[i];
idx = i;
}
}
memset(dist,0,sizeof(dist));
memset(pre,0,sizeof(pre));
pre[idx] = -1;
v = 0;
dfs(idx);
int idx1 = -1;
for(int i = 1;i<=n;i++){
if(dist[i] > v){
v = dist[i];
idx1 = i;
}
}
int ans = 1000000,j = idx1;
for(int i = idx1;i>0;i=pre[i]) {
while(pre[j] && dist[i] - dist[pre[j]]<=s) j =pre[j];
ans = min(ans,max(dist[j],dist[idx1]-dist[i]));
}
for(int i = idx1;i>0;i=pre[i]) vis[i] = 1;
for(int i = idx1;i>0;i=pre[i]) dist[i] = 0, dfs(i);
for(int i = 1;i<=n;i++) ans = max(ans,dist[i]);
cout<<ans<<endl;
return 0;
}
|
总结
对于树的问题，一定要熟悉如何建树，一些相对应的板子要默写的很熟。多敲多练。
