2022 robocom provincial competition solution

T4 Given 6 A team , Let's divide into two non empty groups . The question is very simple. , But there are 6 A rule , Logical judgment is troublesome . I learned something here , All can be liberated into the structure , prioritize , The first one after ranking is the optimal solution .
O(2^6 * log(2 ^ 6))
Code:

#include<bits/stdc++.h>
using namespace std;
int cnt[10];
int a[10][5];
int n,m,k,T;
int ans = 1;
struct node{
    
	int x;
	bool f1,f2,f3; // The rules 0、1、2 
	int dis; // The number of people is poor 
	bool f4; // There are many people on the left 
	vector<int> l;
	bool operator<(const node&rhs)const
	{
    
		if(f1 != rhs.f1) return f1 > rhs.f1;
		if(f2 != rhs.f2) return f2 > rhs.f2;
		if(f3 != rhs.f3) return f3 > rhs.f3;
		if(dis != rhs.dis) return dis < rhs.dis;
		if(f4 != rhs.f4) return f4 > rhs.f4;
		for(int i=0;i<min(l.size(),rhs.l.size());++i)
		{
    
			int t1 = l[i],t2 = rhs.l[i];
			if(t1 != t2) return t1 < t2;
		}
	}
}v[100];
void solve()
{
    
	n = 6;
	for(int i=0;i<n;++i) cin>>cnt[i];
	int t = 0;
	for(int i=0;i<n;++i)
	{
    
		for(int j=0;j<3;++j)
		scanf("%1d",&a[i][j]);
		if(a[i][0]) t++;
	}
	if(t < 2)
	{
    
		cout<<"GG";
		return ;
	}
	for(int i=0;i<(1<<6);++i)
	{
    
		v[i].x = i;
		v[i].f1 = v[i].f2 = v[i].f3 = v[i].f4 = 0;
		int x = i;
		vector<int> l,r;
		for(int i=0;i<n;++i)
		{
    
			if(!cnt[i]) continue;
			if(x>>i&1) l.push_back(i);
			else r.push_back(i);
		}
		if(!l.size() || !r.size()) continue;
		v[i].l = l;
		bool f1 = 0,f2 = 0,f3 = 0,f4 = 0,f5 = 0,f6 = 0;
		int sum1 = 0,sum2 = 0;
		for(int i=0;i<l.size();++i)
		{
    
			int x = l[i];
			if(a[x][0]) f1 = 1;
			if(a[x][1]) f2 = 1;
			if(a[x][2]) f3 = 1;
			sum1 += cnt[x];
		}
		for(int i=0;i<r.size();++i)
		{
    
			int x = r[i];
			if(a[x][0]) f4 = 1;
			if(a[x][1]) f5 = 1;
			if(a[x][2]) f6 = 1;
			sum2 += cnt[x];
		}
		if(f1 && f4) v[i].f1 = 1;
		if(f2 && f3 && f5 && f6) v[i].f2 = 1;
		if(f3 && f6) v[i].f3 = 1;
		v[i].dis = abs(sum1-sum2);
		if(sum1 > sum2) v[i].f4 = 1;
		else v[i].f4 = 0;
	}
	sort(v,v+64);
	int x = v[0].x;
	vector<int> l,r;
	for(int i=0;i<n;++i)
	{
    
		if(!cnt[i]) continue;
		if(x>>i&1) l.push_back(i+1);
		else r.push_back(i+1);
	}
	for(int i=0;i<l.size();++i)
	{
    
		if(i) cout<<" ";
		cout<<l[i];
	}
	cout<<"\n";
	for(int i=0;i<r.size();++i)
	{
    
		if(i) cout<<" ";
		cout<<r[i];
	}
}
signed main(void)
{
    
	solve();
	return 0;
}

T5
The question :
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 .

Ideas : First , A given tree must be a bipartite graph , Because acyclic , The dots on both sides of each edge can be dyed in black and white . that , We can dye the given tree in black and white , Suppose the black node has x individual , White nodes are the rest n-x individual . All black nodes are connected to white nodes , At most x*(n-x), Originally there were n-1 side , The plan is the difference between the two , These edges can be added once respectively .

O(n)
Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
vector<int> va[N];
int n,m,k,T;
bool vis[N];
void dfs(int cur,int fa,bool st)
{
    
	vis[cur] = st;
	for(int i=0;i<va[cur].size();++i)
	{
    
		int j = va[cur][i];
		if(j==fa) continue;
		dfs(j,cur,!st);
	}
}
void solve()
{
    
	cin>>n;
	for(int i=0;i<n-1;++i)
	{
    
		int x,y; cin>>x>>y;
		va[x].push_back(y),va[y].push_back(x);
	}
    dfs(1,0,1);
	int l = 0,r = 0;
	for(int i=1;i<=n;++i)
	{
    
	  if(vis[i]) l++;
	}
	r = n-l;
	long long ans = 1ll*l*r;
	ans -= (n-1);
	cout<<ans;
}
signed main(void)
{
    
	solve();
	return 0;
}