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

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

题目描述

设 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) 视作同一个方案。

输入样例

7
1 2
2 3
2 4
2 5
2 6
4 7
1
2
3
4
5
6
7

输出样例

4
1

思路

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

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

AC代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e6 + 5;

int n;
vector<int> 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<<ans1 * ans2 - n + 1;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33