2022 RoboCom 世界机器人开发者大赛-本科组（省赛）解题报告 | 珂学家

前言

题解

2022 RoboCom 世界机器人开发者大赛-本科组（省赛）。

感觉T5是最简单的，其他都不好做。

RC-u5 树与二分图

分值: 30分

思路: 容斥原理

树天然就是二分图，按深度d归类(偶数深度为S1，奇数深度为S2)，如果新增边，还是二分图，说明

新增边 ( u , v ) , u ∈ S 1 , v ∈ S 2 新增边(u, v), u\in S1, v\in S2 新增边(u,v),u∈S1,v∈S2

只要能梳理出这个性质，那这题就非常的容易。

由容斥得

∣ S 1 ∣ ∗ ∣ S 2 ∣ − ( n − 1 ) |S1| * |S2| - (n - 1) ∣S1∣∗∣S2∣−(n−1)

n 为树的节点， n − 1 为树的边数 n 为树的节点， n-1为树的边数 n为树的节点，n−1为树的边数

S1和S2通过DFS或者bfs层序遍历即可

#include 
using namespace std;
int color[2] = {0};
void dfs(vector&g, vector&color, int u, int fa, int c) {
    color[c]++;
    for (int v: g[u]) {
        if (v == fa) continue;
        dfs(g, color, v, u, 1 - c);
    }
}
int main() {
    int n;
    cin >> n;
    vector g(n);
    vector color(n);
    for (int i = 0; i > u>> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(g, color, 0, -1, 0);
    int64_t p = (int64_t)color[0] * color[1];
        
    cout