当前位置：网站首页>树与二分图【思维】

树与二分图【思维】

2022-07-17 20:46:00 【Codiplay】

题意

给定一颗树，可以在没有直接连边的两个节点上加一条边，满足加边后的图是二分图

思路

一张图是二分图的条件等价于没有奇数环，所以此题要你统计出所有节点个数为偶数的子树

从一个点出发，记录节点个数，注意到如果对于当前这个点来说是奇数个的话，去除掉此点数目一定为偶数，则这个“信息”可以继续被利用。

用异或给每个节点定性，1为奇数0为偶数

从节点1走到节点0所包含的节点一定是偶数个，则是一组为节点个数为偶数的子树，所以：统计一颗树的节点个数为偶数的子树，只需用节点标记为1的数目乘上节点标记为0的数目，得到的便是节点个数为偶数的子树。

题目中说要符合没有直接连边，又因为相邻的节点必一个为0一个为1，数目为2，符合为偶数个的条件，但是有直接连边，所以要去掉边的个数（n - 1）即为答案

代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 100000;
int n, cnt0, cnt1;
vector<int> G[N];
void dfs(int u, int fa, int s)
//这样写不需要再开个vis防止倒退。
//因为是棵树，只需要保证当前节点不会回到fa即可
{
    if(s == 1)cnt1 ++;
    else cnt0 ++;
    for (int i = 0; i < (int)G[u].size(); i ++ )
    {
        if(G[u][i] == fa)continue;
        dfs(G[u][i], u, s ^ 1);
    }
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin >> n;
    for (int i = 1, u, v; i < n; i ++ ) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 1, 1);
    cout << (cnt1 * cnt0) - n + 1 << '\n';
    return 0;
}

原网站

版权声明
本文为[Codiplay]所创，转载请带上原文链接，感谢
https://blog.csdn.net/IsayIwant/article/details/125726448