2022 RoboCom 世界机器人开发者大赛-本科组（省赛）-RC-u5 树与二分图

2022 RoboCom 世界机器人开发者大赛-本科组（省赛）-RC-u5 树与二分图

2022 RoboCom 世界机器人开发者大赛-本科组（省赛）-RC-u5 树与二分图

文章目录

​​2022 RoboCom 世界机器人开发者大赛-本科组（省赛）-RC-u5 树与二分图​​

​​题目描述​​​​输入格式​​​​输出格式​​​​输入样例​​​​输出样例​​​​思路​​​​AC代码​​

题目描述

设 G=(V,E) 是一个无向图，如果顶点集合 V 可分割为两个互不相交的子集 (A,B)，并且每条边 (i,j)∈E 的两个端点 i 和 j 分别属于这两个不同的顶点子集，则称图 G 为一个二分图。

现在给定一棵树 T，要求选择树中两个没有边相连的结点 i 和 j，使得将无向边 (i,j) 加进 T 后能够构成二分图。你的任务是计算满足这个要求的选择方案有多少种。

输入格式

输入第一行给出一个正整数 N (2≤N≤106)，表示树中结点的个数。

接下来 N−1 行，每行给出树中一条边的两端结点编号，以空格分隔。结点编号从 1 开始。题目保证输入给出的是一棵树中所有的边。

输出格式

在一行中输出方案数。注意：连接 (1,2) 和 (2,1) 视作同一个方案。

输入样例

71 22 32 42 52 64 7

输出样例

4

思路

二分图，搜索一下路径就可以了，深度为奇数的点和偶数的点分别染不同的颜色。

ps：比赛的时候用并查集写的，感觉一模一样，但是只有26分?

AC代码

#includeusing namespace std;#define int long longconst int N = 1e6 + 5;int n;vector G[N];int vis[N];int ans1,ans2;void dfs(int now,int depth){ if (depth & 1) ans1 += 1; else ans2 += 1; for (int i : G[now]) { if (vis[i]) continue; vis[i] = true; dfs(i,depth + 1); vis[i] =false; }}signed main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n; for (int i = 1; i < n; ++i) { int f,t;cin>>f>>t; G[f].push_back(t),G[t].push_back(f); } vis[1] = true; dfs(1,1); cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。