BetterJoy完全指南：在PC上完美使用Switch手柄的终极解决方案
2026/7/31 0:51:20
题解题记：码蹄集OJ-斩断灵藤
题目概括：树上分割，每块大小不超过 m，求最少连通块数量
给定一棵 n 个节点的树，允许切断若干边，把树划分成若干连通块；
要求每个连通块内节点数量 ≤ m。
目标：求出分割之后，连通块数量的最小值。
样例：(n=3,m=1)，星型树 (1-2,1-3)；每块最多只能 1 个点，必须全部切开，答案 3。
核心直觉：想要块数最少，就要尽可能让每一块装得尽可能大，属于树上贪心经典模型。
核心思路（后序贪心）
树是无环连通图，采用自底向上后序遍历贪心：
- (dp[u])：以 u 为根的子树中，当前向上连通、还没有被切割出去的连通块大小。
- 处理完 u的所有子节点 v：
- 拿到子节点向上传递的大小 (dp[v])；
- 如果 (dp[u] + dp[v] > m)：必须切断 u-v 这条边，子树单独成为一块，答案 (ans+1)；
- 否则：不切割，合并进当前块，(dp[u] += dp[v])。
- 初始 (dp[u]=1)（节点自身）。
- 遍历全部结束后，根节点所在剩余连通块还没计数，最终
ans+1。
为什么贪心正确？
子树向上传递的块能合并就尽量合并；一旦合并会超限，立刻切分。如果现在不切，往上走只会叠加更多节点，迟早要切，晚切不会得到更优解。
你代码采用的实现方式：拓扑序（叶子剥壳，等价后序 DFS）
因为 (n<=10^6)，递归 DFS 会栈溢出，不能直接写递归后序；
你选择 叶子拓扑剥离（类拓扑排序）实现自底向上遍历：
- 维护节点度数
eg[]，初始叶子（度数 = 1）入队； - 每次取出叶子 u，处理它唯一相邻的父节点；模拟后序顺序；
- 按照上面的合并 / 切割规则更新 dp、统计答案。
题解：
#include<bits/stdc++.h> using namespace std; int main( ) { int n,m; cin>>n>>m; vector<vector<int>>g(n+1); vector<int>eg(n+1); for(int i=0;i<n-1;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); eg[u]++; eg[v]++; } vector<int>dp(n+1); queue<int>q; for(int i=1;i<=n;i++){ if(eg[i]==1){ q.push(i); } } int ans=0; while(!q.empty()){ int u=q.front(); q.pop(); vector<int>temp; //存储子节点 for(int v:g[u]){ if(eg[v]>0){ eg[v]--; } else{ temp.push_back(dp[v]); } if(eg[v]==1){ q.push(v); } } sort(temp.begin(),temp.end()); dp[u]=1; for(int x:temp){ if(dp[u]+x>m){ ans++; } else{ dp[u]+=x; } } eg[u]--; } ans++; cout<<ans<<endl; return 0; }题解题记：最近公共祖先（LCA）
题目：https://www.luogu.com.cn/problem/P2912
题目描述：
共有N头奶牛（2≤N≤1000），编号为 1∼N，它们分别在编号同样为 1∼N的牧场上吃草，其中第i头奶牛位于第i号牧场。
牧场之间由N−1 条双向步道连接。第i条步道连接牧场Ai和Bi，长度为Li（1≤Li≤10000）。
任意两个不同牧场之间有且仅有一条通行路径，因此整张图构成一棵无根树。
现在给出Q组询问，每组询问给定两个牧场编号p1,p2，请你求出这两个牧场之间路径的总长度。
输入格式
- 第一行：两个整数N,Q，分别表示牧场数量与询问组数。
- 第 2∼N行：每行三个整数Ai,Bi,Li，描述一条步道连接的两个牧场以及步道长度。
- 第N+1∼N+Q行：每行两个整数p1,p2，代表一组询问，查询对应两个牧场间的路径长度。
输出格式
- 共Q行，每行输出一个整数，依次表示每组询问的答案，即两点之间路径的总长度。
题记：
默认以节点1为根节点，用dis数组存储节点1到其他节点的距离，定义函数LCA为节点a与节点b的最近公共祖先，则有a，b两点间的距离等于dis[a]+dis[b]-2*dis[LCA(a,b)];并运用倍增法求得两点的最近公共祖先
const int MAXN=1000; //定义MAXN为最深深度，一般来说为20，2^20<10^6 vector<int>deep; //存储每个节点的深度，定义根节点为1 vector<vector<int>>up; //用于存储祖先 //up.resize(MAXN,vector<int>(n)); n为节点数 ，MAXN为祖先数， up[0][i] 表示i的直接祖先，也就是父亲 ; up[1][i]则表示父亲的父亲，即i的爷爷 //所以 初始化up为： up[k][i]=up[k-1][up[k-1][i]]; int lca(int a,int b){ if(deep[a]<deep[b]){ swap(a,b); } for(int i=MAXN-1;i>=0;i--){ if(deep[up[i][a]]>=deep[b]){ a=up[i][a]; } } if(a==b){ return a; } for(int i=MAXN-1;i>=0;i--){ if(up[i][a]!=up[i][b]){ a=up[i][a]; b=up[i][b]; } } return up[0][a]; }题解
#include<bits/stdc++.h> using namespace std; const int MAXN=1010; vector<int>deep; vector<int>dis; vector<vector<int>>up; vector<vector<pair<int,int>>>g; void dfs(int u,int fa){ up[0][u]=fa; for(int i=1;i<MAXN;i++){ up[i][u]=up[i-1][up[i-1][u]]; } for(auto [v,w]:g[u]){ if(v==fa)continue; deep[v]=deep[u]+1; dis[v]=dis[u]+w; dfs(v,u); } } int lca(int a,int b){ if(deep[a]<deep[b]){ swap(a,b); } for(int i=MAXN-1;i>=0;i--){ if(deep[up[i][a]]>=deep[b]){ a=up[i][a]; } } if(a==b){ return a; } for(int i=MAXN-1;i>=0;i--){ if(up[i][a]!=up[i][b]){ a=up[i][a]; b=up[i][b]; } } return up[0][a]; } int main(){ int n,q; cin>>n>>q; g.resize(n+1); for(int i=0;i<n-1;i++){ int u,v,w; cin>>u>>v>>w; g[u].emplace_back(v,w); g[v].emplace_back(u,w); } deep.resize(n+1); dis.resize(n+1); up.resize(MAXN,vector<int>(n+1)); dis[1]=0; deep[1]=1; dfs(1,1); for(int i=0;i<q;i++){ int a,b; cin>>a>>b; int tol=lca(a,b); cout<<dis[a]+dis[b]-2*dis[tol]<<endl; } }题解题记：树的直径
题目：https://www.luogu.com.cn/problem/P4271
题目描述：
给你一棵树，初始没有节点。你需要支持两种操作：
B p表示新建一个节点，将它与p节点连接；若p=−1，则表示不与其它节点相连Q k表示查询在k节点所在的连通块中，距它最远的点的距离。这里距离的定义是两点间经过的边数。
输入格式
第一行一个正整数q，表示操作个数。
接下来q行，每行表示一个操作。
输出格式
对于每个询问操作，输出一行一个整数表示答案。
题记：
此题考查树的直径、树两点间的距离知识，已知树两点（u，v）之间的最长距离为树的直径，树上一点p到其他点的最远距离为一定为该点到直径两端点的距离，即max(dis(u,p),dis(v,p))；
所以此题只需要维护每个连通块中的直径两端点，在查询时输出max(dis(u,p),dis(v,p))即可
还需要运用lca计算两点间的距离
题解：
#include<bits/stdc++.h> using namespace std; const int MAX_LOG = 21; const int MAX_NODE = 1e5 + 10; int up[MAX_LOG][MAX_NODE]; int depth[MAX_NODE]; int fa[MAX_NODE]; // 并查集父节点 int dia_a[MAX_NODE]; // 每个连通块根对应的直径左端点 int dia_b[MAX_NODE]; // 每个连通块根对应的直径右端点 int node_cnt = 0; // 并查集查找（路径压缩） int find(int x) { if (fa[x] != x) fa[x] = find(fa[x]); return fa[x]; } // LCA 查询 int lca(int a, int b) { if (depth[a] < depth[b]) swap(a, b); // 跳到同一深度 int diff = depth[a] - depth[b]; for (int i = 0; i < MAX_LOG; i++) { if (diff >> i & 1) { a = up[i][a]; } } if (a == b) return a; for (int i = MAX_LOG - 1; i >= 0; i--) { if (up[i][a] != up[i][b]) { a = up[i][a]; b = up[i][b]; } } return up[0][a]; } // 计算两点距离 int get_dist(int a, int b) { return depth[a] + depth[b] - 2 * depth[lca(a, b)]; } int main() { ios::sync_with_stdio(false); cin.tie(0); int q; cin >> q; depth[0] = 0; // 显式初始化虚拟节点深度 while (q--) { char op; int p; cin >> op >> p; if (op == 'B') { node_cnt++; int u = node_cnt; fa[u] = u; // 初始化并查集 dia_a[u] = u; // 初始连通块直径端点都是自己 dia_b[u] = u; if (p == -1) { // 独立根节点 depth[u] = 0; up[0][u] = 0; } else { // 接入p所在的树 depth[u] = depth[p] + 1; up[0][u] = p; // 动态预处理倍增祖先 for (int i = 1; i < MAX_LOG; i++) { up[i][u] = up[i-1][up[i-1][u]]; } // 合并到p的连通块 int root = find(p); fa[u] = root; // 取出原连通块直径两端 int a = dia_a[root]; int b = dia_b[root]; int d_old = get_dist(a, b); int d1 = get_dist(a, u); int d2 = get_dist(b, u); // 更新连通块直径 if (d1 > d_old && d1 >= d2) { dia_a[root] = a; dia_b[root] = u; } else if (d2 > d_old) { dia_a[root] = b; dia_b[root] = u; } } } else { // 查询操作 int root = find(p); int a = dia_a[root]; int b = dia_b[root]; cout << max(get_dist(p, a), get_dist(p, b)) << '\n'; } } return 0; }