2022 robocom world robot developer competition - undergraduate group (provincial competition) -- fifth question tree and bipartite diagram (completed)

Other topics

subject

RC-u5 Tree and bipartite graph

set up G=(V,E) It's an undirected graph , If vertex set V It can be divided into two disjoint subsets (A,B), And every side (i,j)∈E Two endpoints of i and j Belong to these two different sets of vertex points , It's called a picture G For a bipartite graph .

Now give a tree T, It is required to select two nodes without edge connection in the tree i and j, Make the undirected edge (i,j) add T Then it can form a bipartite graph . Your task is to calculate how many options meet this requirement .

Input format :
The first line of input gives a positive integer N (2≤N≤1e6), Represents the number of nodes in the tree .

Next N−1 That's ok , Each row gives the node numbers at both ends of an edge in the tree , Space off . Node number from 1 Start . The title ensures that the input gives all the edges of a tree .

Output format :
Output the number of schemes in one row . Be careful ： Connect (1,2) and (2,1) Treat it as the same plan .

sample input :
7
1 2
2 3
2 4
2 5
2 6
4 7
sample output :
4

Answer key

Thought analysis
Bipartite graph , In short , It's the vertex set V It can be divided into two disjoint subsets , Moreover, the two vertices attached to each edge belong to these two disjoint subsets , The vertices in two subsets are not adjacent .

It's not hard to find out , The tree must be a bipartite graph . Because a very important property of a tree is that every node except the root node has only one parent node , So we can put each node in the tree and its parent node into two different sets , Finally, the node set of the whole tree can be divided into two disjoint sets .

So the title means , For a given bipartite graph , How many edges can you add at most so that it is still a bipartite graph

For the number of vertices is n The bipartite graph of , Suppose that the number of vertices of the two sets divided is m , n-m. Obviously, the maximum number of edges of this bipartite graph is m*(n-m), That is, the edge formed by each vertex and all vertices in the opposite set .

thus , We only need any set number , You can calculate the maximum number of sides , Subtracting the number of existing edges is the answer

Key points to achieve

On storage , Although the title is given to a tree , But we should still treat it as a picture , N The larger , So use adjacency table to store graph .

int h[N], e[N], ne[N], idx;

void add(int x, int y)
{
    
    e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}

On the problem of getting the number of vertices in a set , We can traverse the graph with a technique similar to coloring .
Use Boolean true/false To represent two colors , Count only one color .
The color of the adjacency point of the current vertex must be opposite to the current vertex , That is, in another set

bool st[N];
ll m;
void dfs(int v, bool color)
{
    
    st[v] = true;
    if(color) m++;
    for(int i=h[v]; i!=-1; i=ne[i])
    {
    
        int j = e[i];
        if(!st[j]) dfs(j, !color);
    }
}

AC Code

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int N = 1e6 + 10;

ll n;
int h[N], e[N], ne[N], idx;

void add(int x, int y)
{
    
    e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}

bool st[N];
ll m;
void dfs(int v, bool color)
{
    
    st[v] = true;
    if(color) m++;
    for(int i=h[v]; i!=-1; i=ne[i])
    {
    
        int j = e[i];
        if(!st[j]) dfs(j, !color);
    }
}

int main()
{
    
    cin >> n;
    for(int i=1; i<=n; i++) h[i] = -1;
    int x, y;
    for(int i=1; i<n; i++)
    {
    
        cin >> x >> y;
        add(x, y), add(y, x);
    }
    dfs(1, true);// Traverse from any vertex 
    cout << m*(n-m) - (n-1);
    return 0;
}

Be careful m Not for int, Otherwise, the final multiplication will explode

The above code can AC, Welcome to discuss and exchange any questions