首页 > 试题广场 >

小O的树上加边

[编程题]小O的树上加边
  • 热度指数：115 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小O有一棵 n 个点组成的树，树上的点从 1 到 n 编号，树上的边是无向的。任意一棵树都是二分图，小O想知道她最多可以给树加多少条边，使得新的图仍然是二分图。

二分图的定义：如果一个图的所有点可以被分成两个集合 A 和 B，使得所有的边都是一端在 A 中，一端在 B 中，那么这个图就是二分图。

输入描述:
第一行输入一个整数 n\ (1 \leq n \leq 10^5 )，表示树上的点数。
此后 n-1 行，第 i 行输入两个整数 u_i 和 v_i\ (1 \leq u_i, v_i \leq n )，表示树上的一条边连接了点 u_i 和点 v_i。保证这些边可以形成一棵树。


输出描述:
在一行上输出一个正整数，表示最多可以给树加多少条边，使得新的图仍然是二分图。

示例1

输入

4
1 2
2 3
3 4

输出

1

说明

可以添加一条边 (1, 4)，新的图仍然是二分图。
算法知识视频讲解
开通博客
头像 有胆量的柯基在学习
发表于 2025-08-23 12:50:21
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<vector<int>> g(n + 1); for 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-09-11 17:30:41
题目链接 小O的树上加边 题目描述 给定一棵由 个点组成的树。我们知道任何树都是一个二分图。 问题是，我们最多可以向这棵树中添加多少条边，使得新生成的图仍然是一个二分图。 解题思路 这是一个关于二分图性质的典型问题。核心思想是利用树的结构特点来解决。 1. 树与二分图 一个重要的图论性质是：任何树 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

OPPO 树 图 广度优先搜索(BFS)
难度：
0条回答 268浏览

热门推荐

相关试题

小O的树上加边

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号