Bipartite graph matching and tree chain subdivision

Front cheese: bipartite diagram

What is a bipartite graph first

Bipartite graph, also known as bipartite graph, is a special model in graph theory. Let G=(V,E) be an undirected graph. If vertex v can be divided into two disjoint subsets (A,B), and the two vertices i and j associated with each edge (i, J) in the graph belong to these two different vertex sets (i in A,j in B), then graph G is called a bipartite graph.

——Baidu Encyclopedia

A little hard to understand? That is to say, the points in a graph are divided into two parts, and the two points in each part have no edges. The graph after separation is called bipartite graph.

As shown in the figure:

Main course: bipartite graph matching

Concept: given a bipartite graph G, in a subgraph m of G, if any two edges in the edge set {E} of M are not attached to the same vertex, then M is a match.

The next step is how to match - Hungarian algorithm (this is the only one)

The Hungarian algorithm is simply a process of being green and being green.

I don't need professional terms such as Zengguang road. Anyway, the examination room didn't ask us what it was called.

Don't bother to draw a picture, just take the picture of Baidu Encyclopedia.

You may wish to set the node in \ (U \) as \ (U=\left\{1,2,3,4,5\right \} \) from top to bottom, and \ (V=\left\{6,7,8,9\right \} \)

The first is the point \ (1 \), find the point \ (6 \) and match it. Continue with the point \ (2 \), there is also an edge connected to \ (6 \), but it is found that \ (6 \) has been matched, so find out if there are other points to match \ (6 \), but there is no, so find the point \ (1 \) that has been matched with \ (6 \), and \ (1 \) has also been matched. Repeat the above operations. It is found that there are no other points except \ (6 \), indicating that \ (2 \) cannot match \ (6 \), so find the next point \ (7 \), Match it.

Then repeat the above operations until the enumeration is completed. In fact, DFS is a recursive process, so we can use it!

The code is not posted because of my ugly code style. The online code is flying all over the world. In fact, you can think about how to realize it yourself.

Tip: you can use the current arc optimization in network flow.

Let's move on to the next:

Tree chain subdivision

This data structure is very suitable for code farmers

When we encounter the point value summation of a chain \ (x-y \) on a tree, we will intelligently perform a preprocessing, and then \ (ans=sum[x]+sum[y]-sum[lca]-sum[fa[lca]] \)

But what if there are modifications? This method will not work, so we can only introduce a new data structure: tree chain partition.

Main basic operation (operation I can't do basically): transfer the modification on the tree to the DFS sequence of the tree

First, maintain an array \ (son[u] \) to represent the multiple son of \ (U \), that is, the son node with the largest number of nodes. At the same time, it needs \ (size[u],dep[u],fa[u],dfn[u],id[x] \). The first three should not be mentioned\ (dfn[u] \) indicates the subscript of \ (U \) node in DFS order, and \ (id[x] \) is the node with subscript \ (x \) in DFS order.

Pretreatment: twice DFS:

The first time DFS deals with the heavy son, why not deal with it together? Because we want to ensure that a node in the DFS sequence is together with its heavy son, we need to deal with the heavy son array first. The second time DFS is to process DFS sequence. The code is as follows:

void dfs1(int u,int fat)
{
	size[u]=1;
	for(re int v,i=hd[u];i;i=e[i].net)
	{
		v=e[i].v;
		if(v==fat)continue;
		fa[v]=u,dep[v]=dep[u]+1;
		dfs1(v,u);
		size[u]+=size[v];
		if(size[v]>size[son[u]])son[u]=v;
	}
}
void dfs2(int u,int fat)
{
	dfn[u]=++cnt,id[cnt]=u,top[u]=fat;
	if(son[u]==0)return ;
	dfs2(son[u],fat);//Make sure it's with its son
	for(re int v,i=hd[u];i;i=e[i].net)
	{
		v=e[i].v;
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
}

Then use segment tree and tree array to mess with DFS order.

Template example: P3384 Light chain subdivision

This problem is similar to the above problem. There is a subtree to deal with. A little hint: a node is close to the DFS order of its subtree nodes, so you can think about it.

Hand up, yard down:

#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read()
{
	re int x=0,f=1;
	re char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f*=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	return x*f;
}
const int N=100005;
struct edge{int v,net;}e[N<<1];
struct tree{int l,r,val,lazy;}t[N<<3];
int n,m,cnt,a[N],hd[N],dfn[N],top[N],son[N],mod,dep[N],size[N],fa[N],id[N],rt;
inline void ad(int v,int u)
{
	e[++cnt].v=v,e[cnt].net=hd[u],hd[u]=cnt;
	e[++cnt].v=u,e[cnt].net=hd[v],hd[v]=cnt;
}
void dfs1(int u,int fat)
{
	size[u]=1;
	for(re int v,i=hd[u];i;i=e[i].net)
	{
		v=e[i].v;
		if(v==fat)continue;
		fa[v]=u,dep[v]=dep[u]+1;
		dfs1(v,u);
		size[u]+=size[v];
		if(size[v]>size[son[u]])son[u]=v;
	}
}
void dfs2(int u,int fat)
{
	dfn[u]=++cnt,id[cnt]=u,top[u]=fat;
	if(son[u]==0)return ;
	dfs2(son[u],fat);
	for(re int v,i=hd[u];i;i=e[i].net)
	{
		v=e[i].v;
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
}
inline void Down(int x)
{
	if(t[x].lazy)
	{
		(t[x<<1].lazy+=t[x].lazy)%=mod,(t[x<<1|1].lazy+=t[x].lazy)%=mod;
		(t[x<<1].val+=t[x].lazy*(t[x<<1].r-t[x<<1].l+1)%mod)%=mod,(t[x<<1|1].val+=t[x].lazy*(t[x<<1|1].r-t[x<<1|1].l+1)%mod)%=mod;
		t[x].lazy=0;
	}
}
int query(int l,int r,int x)
{
	if(l<=t[x].l&&t[x].r<=r)return t[x].val;
	Down(x);
	re int sum=0;
	if(t[x<<1].r>=l)(sum+=query(l,r,x<<1))%=mod;
	if(t[x<<1|1].l<=r)(sum+=query(l,r,x<<1|1))%=mod;
	return sum%mod;
}
void add(int l,int r,int x,int val)
{
	if(l<=t[x].l&&t[x].r<=r)
	{
		(t[x].lazy+=val)%=mod,(t[x].val+=val*(t[x].r-t[x].l+1)%mod)%=mod;
		return ;
	}
	Down(x);
	if(t[x<<1].r>=l)add(l,r,x<<1,val);
	if(t[x<<1|1].l<=r)add(l,r,x<<1|1,val);
	t[x].val=(t[x<<1].val+t[x<<1|1].val)%mod;
}
inline void query_add(int x,int y,int val)
{
	re int fx=top[x],fy=top[y];
	for(;fx^fy;)
	{
		if(dep[fx]>=dep[fy])
		{
			add(dfn[fx],dfn[x],1,val);
			x=fa[fx],fx=top[x];
		}
		else
		{
			add(dfn[fy],dfn[y],1,val);
			y=fa[fy],fy=top[y];
		}
	}
	if(dfn[x]<dfn[y])add(dfn[x],dfn[y],1,val);
	else add(dfn[y],dfn[x],1,val);
}
inline int query_sum(int x,int y)
{
	re int fx=top[x],fy=top[y],sum=0;
	for(;fx^fy;)
	{
		if(dep[fx]>=dep[fy])
		{
			(sum+=query(dfn[fx],dfn[x],1))%=mod;
			x=fa[fx],fx=top[x];
		}
		else
		{
			(sum+=query(dfn[fy],dfn[y],1))%=mod;
			y=fa[fy],fy=top[y];
		}
	}
	if(dfn[x]<dfn[y])(sum+=query(dfn[x],dfn[y],1))%=mod;
	else (sum+=query(dfn[y],dfn[x],1))%=mod;
	return sum;
}
void build(int l,int r,int x)
{
	t[x].l=l,t[x].r=r;
	if(l>r)return ;
	else if(l==r)
	{
		t[x].val=a[id[l]];
		return ;
	}
	re int mid=(l+r)>>1;
	build(l,mid,x<<1);
	build(mid+1,r,x<<1|1);
	t[x].val=(t[x<<1].val+t[x<<1|1].val)%mod;
}
int main()
{
	n=read(),m=read(),rt=read(),mod=read();
	for(re int i=1;i<=n;i++)a[i]=read();
	for(re int i=1;i<n;i++)ad(read(),read());
	cnt=0,dfs1(rt,0),dfs2(rt,rt),build(1,n,1);
	for(re int type,x,y,z,i=1;i<=m;i++)
	{
		type=read(),x=read();
		if(type==1)
		{
			y=read(),z=read();
			query_add(x,y,z);
		}
		else if(type==2)
		{
			y=read();
			printf("%d\n",query_sum(x,y));
		}
		else if(type==3)
		{
			z=read();
			add(dfn[x],dfn[x]+size[x]-1,1,z);
		}
		else printf("%d\n",query(dfn[x],dfn[x]+size[x]-1,1));
	}
	return 0;
}

Posted by bravo14 on Fri, 20 May 2022 16:59:44 +0300