2 solutions
-
7
直径解法
建议不要看他们的代码，码风真的一坨。看讲解扎布多德勒。
而且我对比了一下，多份代码不得不说肉眼还是能发现亿点点相似性（沉思）。由外向内砍叶结点的做法，代码和思路都比较简洁清晰，看题解即可：
直径解法看我的代码（自荐）。一定要掌握！
可以帮助你深入理解直径的性质，也可以帮助你做 P1099 树网的核 这题。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; vector<int> g[N]; int d[N]; // 记录与当前轮DFS源点的距离 int r[N]; // 记录直径的路径 int A, B; // 记录直径的两个端点 int n, k; int center; // 树的中心 int maxd[N]; // 每个结点能到达的最远的叶结点的深度 int dis[N]; // 存储 maxd[u]-d[u]，用于排序 void build() { int u, v; for (int i = 1; i < n; i++) { cin >> u >> v; g[u].emplace_back(v); g[v].emplace_back(u); } } // 找树的直径 // u是当前结点，f是u的父节点 void dfs(int u, int f) { for (auto v : g[u]) { if (v == f) continue; d[v] = d[u] + 1; if (d[v] > d[A]) A = v; r[v] = u; dfs(v, u); } } // 计算每个结点到中心的距离（以中心为根的结点深度） // 同时计算每个结点能到达的最远的叶结点的深度 void calc(int u, int f) { maxd[u] = d[u]; // 当然也可以不记深度，而是最远的叶结点与u的距离，后面就不用减了 for (auto v : g[u]) { if (v == f) continue; d[v] = d[u] + 1; calc(v, u); // 递归回来后统计最远叶结点深度 maxd[u] = max(maxd[u], maxd[v]); } } int main() { cin >> n >> k; build(); // 1. 找直径 dfs(1, 0); B = A; d[A] = 0, r[A] = 0; dfs(A, 0); // debug // cout << d[A] << '\n'; // int pre = A, len = d[A] + 1; // while (len--) { // cout << pre << ' '; // pre = r[pre]; // } // 2. 找树的中心 center = A; int len = (d[A] + 1) / 2; while (len--) center = r[center]; // cout << center; // 3. 计算每个结点能到达的最远的叶结点的深度 memset(d, 0, sizeof d); calc(center, 0); // 4. 计算选点依据是距离 maxd[u]-d[u] for (int i = 1; i <= n; i++) dis[i] = maxd[i] - d[i]; sort(dis + 1, dis + n + 1); // 非核心城市与核心城市群的最大距离等于 dis[x]+1 // （x到核心城市群还需要经过一条边） cout << dis[n - k] + 1; return 0; }-
C23huangminzhe @ 2025-1-15 13:04:22
这个λ的题解好详细！，直接好评 👍
-
C23panweiming
@ 2025-1-15 13:54:00
插屏
-
C23panweiming
@ 2025-1-15 19:57:24
免费赠送氢锡版呆马
#include<iostream> #include<vector> #include<algorithm> #include<cstring> #define N 100005 using namespace std; int n,k,lp,rp,c; vector<int>g[N]; int dis[N]; int d[N]; int ma[N]; int road[N]; void add(int u,int v) { g[u].push_back(v); g[v].push_back(u); } void dfs(int x,int fa) { for(auto i:g[x]) { if(i==fa)continue; dis[i]=dis[x]+1; if(dis[i]>dis[lp])lp=i; road[i]=x; dfs(i,x); } } void dfs(int x) { dis[x]=0; road[x]=0; dfs(x,0); } void calc(int x,int fa) { ma[x]=dis[x]; for(auto i:g[x]) { if(i==fa)continue; dis[i]=dis[x]+1; calc(i,x); ma[x]=max(ma[x],ma[i]); } } int main() { cin>>n>>k; for(int i=1;i<n;i++) { int u,v; cin>>u>>v; add(u,v); } dfs(1); rp=lp; dfs(lp); c=lp; int len=(dis[lp]+1)/2; while(len--)c=road[c]; memset(dis,0,sizeof dis); calc(c,0); for(int i=1;i<=n;i++)d[i]=ma[i]-dis[i]; sort(d+1,d+1+n); cout<<d[n-k]+1; return 0; } -
C23panweiming
@ 2025-1-16 16:46:33
注：本题解只是优化 ZFJ 的题解。
优化了注释和 calc()，思路看注释。
代码 #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; vector a[N]; // 图 int dia[N],dia1,dia2; // 直径路径和它的两个端点 int dis[N]; // 与指定点的距离 int centre; // 树的中心 void dfs(int u,int f){ for (int i = 0;i < a[u].size();i++){ int v = a[u][i]; if (v != f){ dis[v] = dis[u] + 1; if (dis[v] > dis[dia1]) dia1 = v; dia[v] = u; dfs(v,u); } } } // 每个点到中心的距离，和每个点到它子辈中离它最远的叶结点的距离 void calc(int u,int f){ for (int i = 0;i < a[u].size();i++){ int v = a[u][i]; if (v != f){ calc(v,u); dis[u] = max(dis[u],dis[v] + 1); } } } int main(int argc, char **argv){ int n,k; cin >> n >> k; for (int i = 1;i < n;i++){ int u,v; cin >> u >> v; a[u].push_back(v); a[v].push_back(u); } // 找直径 // 当前指定点为 dia1 dfs(1,0); dia2 = dia1,dis[dia1] = 0,dia[dia1] = 0; dfs(dia1,0);
// 找中心 centre = dia1; int len = (dis[dia1] + 1) / 2; while (len--) centre = dia[centre]; // 每个点到中心的距离 // 当前指定点为：以 i 为根时，它到离它最远的叶结点的距离 memset(dis,0,sizeof dis); calc(centre,0); // printf("%d\n",centre); // for (int i = 1;i <= n;i++){ // printf("%d ",dis[i]); // } // 这里越大的 dis[i] 越靠近中心城市，排掉 k 个中心城市就是最大的到中心城市的距离。 // +1 就是到中心城市的距离 sort(dis + 1,dis + n + 1); cout << dis[n - k] + 1; return 0;}
-
zengfj @ 2025-1-16 17:47:52
-
C24zhuchengyu
@ 2025-1-17 14:05:47
-
zengfj
LV 7
MOD
@ 2025-1-15 11:19:41
