# Bipartite graph matching and tree chain subdivision

## Front cheese: bipartite diagram

### As shown in the figure: # Tree chain subdivision

### 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);
}
}


# Template example: P3384 Light chain subdivision

## Hand up, yard down:

#include<bits/stdc++.h>
#define re register
using namespace std;
{
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;
{
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);
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])
{
x=fa[fx],fx=top[x];
}
else
{
y=fa[fy],fy=top[y];
}
}
}
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()
{
cnt=0,dfs1(rt,0),dfs2(rt,rt),build(1,n,1);
for(re int type,x,y,z,i=1;i<=m;i++)
{
if(type==1)
{
}
else if(type==2)
{
printf("%d\n",query_sum(x,y));
}
else if(type==3)
{