CF2131D Arboris Contractio-北京尧图网络

题目描述Kagari 正准备对一棵树进行归档她知道归档的成本取决于树的直径 ¹。为了降低成本她的目标是首先尽可能缩小直径。她可以对树执行以下操作选择两个顶点 s 和 t。设从 s 到 t 的简单路径 ² 上的顶点序列为 v0,v1,…,vk其中 v0s,vkt。移除路径上的所有边。即移除边 (v0,v1),(v1,v2),…,(vk−1,vk)。将顶点 v1,v2,…,vk 直接连接到 v0。即添加边 (v0,v1),(v0,v2),…,(v0,vk)。可以证明操作后图仍然是一棵树。请帮助她确定实现最小直径所需的最少操作次数。注释¹ 树的直径是任意两个顶点之间可能的最长距离。距离本身通过连接它们的唯一简单路径上的边数来衡量。² 简单路径是树中两个顶点之间的路径且不会重复访问任何顶点。可以证明任意两个顶点之间的简单路径总是唯一的。输入格式每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤104)。每个测试用例的第一行包含一个整数 n(2≤n≤2⋅105)表示树中顶点的数量。每个测试用例的接下来 n−1 行描述树。每行包含两个整数 u 和 v(1≤u,v≤n,uv)表示顶点 u 和 v 之间有一条边。保证这些边构成一棵树。保证所有测试用例的 n 之和不超过 2⋅105。输出格式对于每个测试用例输出一个整数表示实现最小直径所需的最少操作次数。输入输出样例输入 #1复制4 4 1 2 1 3 2 4 2 2 1 4 1 2 2 3 2 4 11 1 2 1 3 2 4 3 5 3 8 5 6 5 7 7 9 7 10 5 11输出 #1复制1 0 0 4说明/提示在第一个测试用例中原始树的直径为 3。Kagari 可以对 s3 和 t4 执行操作。操作包括以下步骤移除边 (3,1), (1,2) 和 (2,4)。添加边 (3,1), (3,2) 和 (3,4)。操作后直径减小到 2。可以证明 2 是最小直径。在第二个测试用例中树的直径为 1。可以证明 1 已经是最小值因此 Kagari 无需执行操作。每次操作选择两个顶点 s 和 t。设从 s 到 t 的简单路径 ² 上的顶点序列为 v0,v1,…,vk其中 v0s,vkt。移除路径上的所有边。即移除边 (v0,v1),(v1,v2),…,(vk−1,vk)。将顶点 v1,v2,…,vk 直接连接到 v0。即添加边 (v0,v1),(v0,v2),…,(v0,vk)。即把一条链“压扁”成以起点为中心的星形。#include bits/stdc.h #define int long long using namespace std; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //这个记得注释掉 //freopen(../input.txt,r,stdin); int t; cint; while (t--) { //cout------------------------\n; int n; cinn; vectorvectorintg(n1); vectorintin(n1);//记录每个点连了多少个点 for (int i1;in-1;i) { int u,v; cinuv; g[u].push_back(v); g[v].push_back(u); in[u]; in[v]; } //统计整棵树有多少个叶子 int cnt_leaf0; for (int i1;in;i) { //度数为 1 的节点就是叶子 if (in[i]1) cnt_leaf; } //找直连叶子最多的点作为根 int max_leaf0; for (int u1;un;u) { //当前叶子u周围直接连着几个叶子 int cur_leaf0; for (int v:g[u]) { //度数为 1 的节点就是叶子 if (in[v]1) cur_leaf; } if (cur_leafmax_leaf) max_leafcur_leaf; } //叶子总数-已经直连当前中心的叶子数 int anscnt_leaf-max_leaf; if (n2)//特判 ans0; coutans\n; } return 0; }

CF2131D Arboris Contractio

相关推荐

OpenCV 低代码工作流框架的核心思路是：用可视化节点编排代替手写算子代码，用工作流文件（.vm）承载算法逻辑，上层应用只负责加载和执行

打卡信奥刷题（3610）用C++实现信奥题 P11725 [JOIG 2025] 修学旅行 / School Trip

第二节【Git基础篇】Git入门实战：安装、初始化与核心命令学习

更多资讯

CKEditor实现PPT图片粘贴上传：从剪贴板原理到工程落地

教育平台PPT图片粘贴到CKEditor的完整实现方案

Codex 安装 Agent 工具包与 MCP 配置实战指南

e0e1-wx 新版指南：微信小程序 wxapkg 反编译流程与避坑

DevExpress VCL Controls v25.2.3 全系安装与源码调试指南

hyperframes 实战：HTML 转 MP4 的 CLI 工具链与 AI 代理集成

今日更新

Multisim仿真NE555 PWM控制器：从搭电路到调占空比全流程

S32K312 AUTOSAR BSW开发实战：从配置踩坑到烧录交付

双目视觉三维人脸重建：从视差图到点云粗配准全流程解析

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？