题解题记码蹄集OJ-斩断灵藤题目概括树上分割每块大小不超过 m求最少连通块数量给定一棵 n 个节点的树允许切断若干边把树划分成若干连通块要求每个连通块内节点数量 ≤ m。目标求出分割之后连通块数量的最小值。样例(n3,m1)星型树 (1-2,1-3)每块最多只能 1 个点必须全部切开答案 3。核心直觉想要块数最少就要尽可能让每一块装得尽可能大属于树上贪心经典模型。核心思路后序贪心树是无环连通图采用自底向上后序遍历贪心(dp[u])以 u 为根的子树中当前向上连通、还没有被切割出去的连通块大小。处理完 u的所有子节点 v拿到子节点向上传递的大小 (dp[v])如果 (dp[u] dp[v] m)必须切断 u-v 这条边子树单独成为一块答案 (ans1)否则不切割合并进当前块(dp[u] dp[v])。初始 (dp[u]1)节点自身。遍历全部结束后根节点所在剩余连通块还没计数最终ans1。为什么贪心正确子树向上传递的块能合并就尽量合并一旦合并会超限立刻切分。如果现在不切往上走只会叠加更多节点迟早要切晚切不会得到更优解。你代码采用的实现方式拓扑序叶子剥壳等价后序 DFS因为 (n10^6)递归 DFS 会栈溢出不能直接写递归后序你选择 叶子拓扑剥离类拓扑排序实现自底向上遍历维护节点度数eg[]初始叶子度数 1入队每次取出叶子 u处理它唯一相邻的父节点模拟后序顺序按照上面的合并 / 切割规则更新 dp、统计答案。题解#includebits/stdc.h using namespace std; int main( ) { int n,m; cinnm; vectorvectorintg(n1); vectorinteg(n1); for(int i0;in-1;i){ int u,v; cinuv; g[u].push_back(v); g[v].push_back(u); eg[u]; eg[v]; } vectorintdp(n1); queueintq; for(int i1;in;i){ if(eg[i]1){ q.push(i); } } int ans0; while(!q.empty()){ int uq.front(); q.pop(); vectorinttemp; //存储子节点 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]xm){ ans; } else{ dp[u]x; } } eg[u]--; } ans; coutansendl; 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长度为Li1≤Li≤10000。任意两个不同牧场之间有且仅有一条通行路径因此整张图构成一棵无根树。现在给出Q组询问每组询问给定两个牧场编号p1,p2请你求出这两个牧场之间路径的总长度。输入格式第一行两个整数N,Q分别表示牧场数量与询问组数。第 2∼N行每行三个整数Ai,Bi,Li描述一条步道连接的两个牧场以及步道长度。第N1∼NQ行每行两个整数p1,p2代表一组询问查询对应两个牧场间的路径长度。输出格式共Q行每行输出一个整数依次表示每组询问的答案即两点之间路径的总长度。题记默认以节点1为根节点用dis数组存储节点1到其他节点的距离定义函数LCA为节点a与节点b的最近公共祖先则有ab两点间的距离等于dis[a]dis[b]-2*dis[LCA(a,b)];并运用倍增法求得两点的最近公共祖先const int MAXN1000; //定义MAXN为最深深度一般来说为202^2010^6 vectorintdeep; //存储每个节点的深度定义根节点为1 vectorvectorintup; //用于存储祖先 //up.resize(MAXN,vectorint(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 iMAXN-1;i0;i--){ if(deep[up[i][a]]deep[b]){ aup[i][a]; } } if(ab){ return a; } for(int iMAXN-1;i0;i--){ if(up[i][a]!up[i][b]){ aup[i][a]; bup[i][b]; } } return up[0][a]; }题解#includebits/stdc.h using namespace std; const int MAXN1010; vectorintdeep; vectorintdis; vectorvectorintup; vectorvectorpairint,intg; void dfs(int u,int fa){ up[0][u]fa; for(int i1;iMAXN;i){ up[i][u]up[i-1][up[i-1][u]]; } for(auto [v,w]:g[u]){ if(vfa)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 iMAXN-1;i0;i--){ if(deep[up[i][a]]deep[b]){ aup[i][a]; } } if(ab){ return a; } for(int iMAXN-1;i0;i--){ if(up[i][a]!up[i][b]){ aup[i][a]; bup[i][b]; } } return up[0][a]; } int main(){ int n,q; cinnq; g.resize(n1); for(int i0;in-1;i){ int u,v,w; cinuvw; g[u].emplace_back(v,w); g[v].emplace_back(u,w); } deep.resize(n1); dis.resize(n1); up.resize(MAXN,vectorint(n1)); dis[1]0; deep[1]1; dfs(1,1); for(int i0;iq;i){ int a,b; cinab; int tollca(a,b); coutdis[a]dis[b]-2*dis[tol]endl; } }题解题记树的直径题目https://www.luogu.com.cn/problem/P4271题目描述给你一棵树初始没有节点。你需要支持两种操作B p表示新建一个节点将它与p节点连接若p−1则表示不与其它节点相连Q k表示查询在k节点所在的连通块中距它最远的点的距离。这里距离的定义是两点间经过的边数。输入格式第一行一个正整数q表示操作个数。接下来q行每行表示一个操作。输出格式对于每个询问操作输出一行一个整数表示答案。题记此题考查树的直径、树两点间的距离知识已知树两点uv之间的最长距离为树的直径树上一点p到其他点的最远距离为一定为该点到直径两端点的距离即max(dis(u,p),dis(v,p))所以此题只需要维护每个连通块中的直径两端点在查询时输出max(dis(u,p),dis(v,p))即可还需要运用lca计算两点间的距离题解#includebits/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; }