UOJ 207 共价大爷游长沙题解

xiaoh 2020-5-23

题意

给定一棵有 $n$ 个点的树( $1\leq n\leq 100000$ ),树的形态会动态变化.现有一个动态变化的点对集 $s$ ,每次询问一条边 $(u_i,v_i)$ ,要求输出这个点是否在点对集中所有点对间的路径上.

题解

树的形态会变化,显然考虑使用 $LCT$ .那么点对集怎么维护呢?想到可以使用随机化的思想来处理.每次增加点对时,给这条路径附上一个随机权值并将路径上所有边异或上这个权值.那么当询问时,若询问的边的边权等于所有路径的异或和,那么这个点有大概率是所有路径都经过的.那么为了尽可能的防止哈希碰撞,我们只要将边权开大到long long就可以了.

接下来考虑树的边权改变时该如何处理.我们发现加上某一条边后,原图出现了一个环,而被删边的路径上的点都会经过环上的除该边外的其他所有边,我们只要将删除那条边,并把它的的边权异或给环上其余的边就行了.时间复杂度 $O(n\log n)$ .(当然这是一个长达 $1s$ 的 $n\log n$ )

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=100010,MAXM=300010;
int tot=0;
int n,m;
int val[MAXN*2+MAXM],sum[MAXN*2+MAXM],ch[MAXN*2+MAXM][2],f[MAXN*2+MAXM];
int tag[MAXN*2+MAXM],tag2[MAXN*2+MAXM];
inline void pushup(register int x)
{
    sum[x]=sum[ch[x][0]]^sum[ch[x][1]];
    if(x>n) sum[x]^=val[x];
}
inline int get(register int x)
{
    return x==ch[f[x]][1];
}
inline int isroot(register int x)
{
    return x!=ch[f[x]][0]&&x!=ch[f[x]][1];
}
inline void rotate(register int x)
{
    register int y=f[x],z=f[y],chk=get(x);
    if(!isroot(y)) ch[z][y==ch[z][1]]=x;
    ch[y][chk]=ch[x][chk^1],f[ch[x][chk^1]]=y;
    ch[x][chk^1]=y,f[y]=x;
    f[x]=z;
    pushup(y),pushup(x);
}
inline void pushdown(register int x)
{
    if(tag[x])
    {
        swap(ch[ch[x][0]][0],ch[ch[x][0]][1]);
        swap(ch[ch[x][1]][0],ch[ch[x][1]][1]);
        tag[ch[x][0]]^=1,tag[ch[x][1]]^=1;
        tag[x]=0;
    }
    val[ch[x][0]]^=tag2[x],val[ch[x][1]]^=tag2[x];
    sum[ch[x][0]]^=tag2[x],sum[ch[x][1]]^=tag2[x];
    tag2[ch[x][0]]^=tag2[x],tag2[ch[x][1]]^=tag2[x];
    tag2[x]=0,val[0]=sum[0]=0;
}
void update(register int x)
{
    if(!isroot(x)) update(f[x]);
    pushdown(x);
}
inline void Splay(register int x)
{
    update(x);
    for(register int fa=f[x];fa=f[x],!isroot(x);rotate(x))
    if(!isroot(fa)) rotate(get(x)==get(fa)? fa:x);
}
inline int Access(register int x)
{
    register int ret=0;
    for(;x;ret=x,x=f[x])
    Splay(x),ch[x][1]=ret,pushup(x);
    return ret;
}
inline void makeroot(register int x)
{
    x=Access(x);
    swap(ch[x][0],ch[x][1]);
    tag[x]^=1;
}
inline void Link(register int x,register int y)
{
    makeroot(x),Splay(x),f[x]=y;
}
inline void split(register int x,register int y)
{
    makeroot(x),Access(y),Splay(y);
}
inline void Cut(register int x,register int y)
{
    split(x,y);
    register int chk=get(x);
    f[x]=ch[y][chk]=0;
}
map<pair<int,int>,int> mp;
long long cur=0;
inline long long Random()
{
    return rand()*RAND_MAX+rand();
}
int cnt=0;
struct node{
	int x,y;
	long long val;
}a[MAXM];
int main()
{
	srand(time(0));
    read(n);
    read(n),read(m);
    for(register int i=1;i<n;++i)
    {
        ++tot;
        int u,v;
        read(u),read(v);
        if(u>v) swap(u,v);
        Link(u,n+tot),Link(n+tot,v);
        mp[make_pair(u,v)]=tot;
    }
    for(register int i=1;i<=m;++i)
    {
        int op;
        read(op);
        if(op==1)
        {
            int u,v,x,y;
            read(u),read(v),read(x),read(y);
            if(u>v) swap(u,v);
            if(x>y) swap(x,y);
            int pos=mp[make_pair(u,v)];
			split(u,v);
			long long tmp=sum[v];
            Cut(u,n+pos),Cut(n+pos,v);
            ++tot;
            Link(x,n+tot),Link(n+tot,y);
			split(u,v);
			sum[v]^=tmp,tag2[v]^=tmp;
            mp[make_pair(x,y)]=tot;
        }
        else if(op==2)
        {
            int x,y;
            read(x),read(y);
            if(x>y) swap(x,y);
            long long tmp=Random();
            a[++cnt]={x,y,tmp};
            split(x,y);
            tag2[y]^=tmp,sum[y]^=tmp;
            cur^=tmp;
        }
        else if(op==3)
        {
            int x,y;
            read(x);
            long long tmp=a[x].val;
			y=a[x].y,x=a[x].x;
            split(x,y);
			cur^=tmp;
            tag2[y]^=tmp,sum[y]^=tmp;
        }
        else
        {
            int x,y;
            read(x),read(y);
            split(x,y);
            if(sum[y]==cur) printf("YES\n");
            else printf("NO\n");
        }
    }
	return 0;
}

UOJ 207 共价大爷游长沙 题解

xiaoh 2020-5-23

题意

题解

Code

UOJ 207 共价大爷游长沙题解