[ahoi2005] route planning

Dynamic maintenance tree

link ：P2542 [AHOI2005] Route planning - Luogu | New ecology of computer science education (luogu.com.cn)

The question ： Given a simple undirected graph , Ask or modify many times . Ask about the number of critical paths between two points , Or break an edge . The critical path is the edge that two points must pass through in any link .

Answer key ： Observation inquiry , The critical path is the longest path between two points at most . Assign values to each edge at the beginning 1 , When the two points are in different connection blocks, the link is OK . If it exists in the same connecting block , Then all the edge weights between the two points are changed to 0 , Because the existence of this edge will make the critical path between two points no longer exist . In this way, use trees to cut or LCT All can be maintained . At the same time, the operation of deleting edges is changed to that of adding edges , Just reverse all queries or modifications . use LCT For maintenance, you only need to download the clear mark .

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<set>

using namespace std;
const int maxn=2e5+5;
const int N=3e4+5;

namespace IO{
    
	char buf[1<<20],*P1=buf,*P2=buf;
// #define gc() getchar()
	#define gc() (P1==P2&&(P2=(P1=buf)+fread(buf,1,1<<20,stdin),P1==P2)?EOF:*P1++)
	#define TT template<class T>inline
	TT bool read(T&x)
	{
    
    	x=0; char c=gc(); bool f=0;
    	while(c<48||c>57){
    f^=c=='-',c=gc();}
    	while(47<c&&c<58)x=(x<<3)+(x<<1)+(c^48),c=gc();
    	if(f)x=-x;
		return x!=-1;
	}
	TT void print(T x)
	{
     
		int t[30]={
    0},cnt=0;
		while(x)t[++cnt]=x%10,x/=10;
		if(!cnt)putchar('0');
		else while(cnt)putchar(t[cnt--]+'0');
		puts("");
	}
};
using namespace IO;

int ans[maxn],n,m,q,op,u,v,w;
int f[maxn],c[maxn][2],a[maxn],s[maxn],st[maxn];
bool r[maxn],tg[maxn];
#define lc c[x][0]
#define rc c[x][1]
struct node{
    
	int op,u,v;
	inline bool operator<(const node&x)const{
    
		return u!=x.u?u<x.u:v<x.v;
	}
}ed[maxn],t[maxn];
set<node>bt;

bool nroot(int x)
{
    
	return c[f[x]][0]==x||c[f[x]][1]==x;
}

void pushup(int x)
{
    
	s[x]=s[lc]+s[rc]+a[x];
}

void reverse(int x)
{
    
	swap(lc,rc); r[x]^=1;
}

void down(int x)
{
    
	s[x]=a[x]=0,tg[x]=1;
}

void pushdown(int x)
{
    
	if(tg[x])
	{
    
		if(lc)down(lc);
		if(rc)down(rc);
		tg[x]=0;
	}
	if(r[x])
	{
    
		if(lc)reverse(lc);
		if(rc)reverse(rc);
		r[x]=0;
	}
}

void rotate(int x)
{
    
	int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
	if(nroot(y))c[z][c[z][1]==y]=x; 
	c[x][!k]=y,c[y][k]=w;
	if(w)f[w]=y; f[y]=x,f[x]=z;
	pushup(y);
}

void splay(int x)
{
    
	int y=x,z=0;
	st[++z]=y;
	while(nroot(y))st[++z]=y=f[y];
	while(z)pushdown(st[z--]);
	while(nroot(x))
	{
    
		y=f[x],z=f[y];
		if(nroot(y))
		{
    
			rotate((c[y][0]==x)^(c[z][0]==y)?x:y);
		}
		rotate(x);
	}
	pushup(x);
}

void access(int x)
{
    
	for(int y=0;x;x=f[y=x])
	{
    
		splay(x),rc=y,pushup(x);
	}
}

void makeroot(int x)
{
    
	access(x),splay(x),reverse(x);
}

int findroot(int x)
{
    
	access(x),splay(x);
	while(lc)pushdown(x),x=lc;
	splay(x); return x;
}

void split(int x,int y)
{
    
	makeroot(x),access(y),splay(y);
}

bool link(int x,int y,int o)
{
    
	makeroot(x);
	if(findroot(y)!=x)
	{
    
		if(o)f[x]=y; return true;
	}
	return false;
}

void cut(int x,int y)
{
    
	makeroot(x);
	if(findroot(y)==x&&f[y]==x&&!c[y][0])
	{
    
		f[y]=c[x][1]=0; pushup(x);
	}
}

int main()
{
    
	read(n),read(m);
	for(int i=n+1;i<=n+m;i++)
	{
    
		read(ed[i].u),read(ed[i].v),a[i]=1;
	}
	while(read(t[++q].op))
	{
    
		read(t[q].u),read(t[q].v);
		if(!t[q].op)bt.insert(t[q]); 
	}
	int cnt=0; q--;
	for(int i=n+1;i<=n+m;i++)
	{
    
		if(bt.find(ed[i])!=bt.end())continue;
		if(cnt<n&&link(ed[i].u,ed[i].v,0))
		{
    
			cnt++,link(ed[i].u,i,1),link(ed[i].v,i,1);
		}
		else 
		{
    
			split(ed[i].u,ed[i].v),down(ed[i].v);
		}
	}
	for(int i=q;i>=1;i--)
	{
    
		if(t[i].op)
		{
    
			split(t[i].u,t[i].v),ans[i]=s[t[i].v];
		}
		else
		{
    
			split(t[i].u,t[i].v),down(t[i].v);
		}
	}
	for(int i=1;i<=q;i++)
	{
    
		if(t[i].op)cout<<ans[i]<<"\n";
	}
	return 0;
}