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

---

前言

---

题解

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

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

---

RC-u5 树与二分图

分值: 30分

思路: 容斥原理

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

$$新增边(u,v),u\in S1,v\in S2$$

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

由容斥得

$$|S1|\ast |S2|-(n-1)$$
$$n为树的节点，n-1为树的边数$$

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

#include <bits/stdc++.h>using namespace std;int color[2] = {0};void dfs(vector<vector<int>>&g, vector<int>&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<vector<int>> g(n);vector<int> color(n);for (int i = 0; i < n - 1; i++) {int u, v;cin >> 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 << (p-(n - 1)) << "\n";return 0;
}

---

写在最后