一颗会动的树。 有一个点对集合会变。 每次询问一条树边，问集合内所有点对之间的路径是否都经过该边。
终于无聊来补了这题 每个点对随机一个10^9内的权值 然后给两端点的点权分别异或给权值。 询问一条边是否被全部经过，就是询问每个点对是否都被这条边分开。 那么比如这条边是(u,v)，断开后u的子树异或和应该要等于当前所有路径权值异或和。 就可以判了，出错率当然是很低啦。
#include<cstdio>#include<algorithm>#include<ctime>#define fo(i,a,b) for(i=a;i<=b;i++)using namespace std;typedef long long ll;const int maxn=100000+10,maxm=300000+10,md=1000000000;int ask[maxm][5],size[maxm*4],c[maxm],b[maxm];int key[maxn],num[maxn],siz[maxn],father[maxn],tree[maxn][2],pp[maxn],sum[maxn],sta[maxn];bool bz[maxn];int h[maxn],go[maxn*2],next[maxn*2];int i,j,k,u,v,l,t,n,m,tot,top,wdc,ans,id;int random(int x){ ll t=rand()%10000; t=t*10000+rand()%10000; t=t*10000+rand()%10000; return t%x;}int read(){ int x=0,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-'0'; ch=getchar(); } return x*f;}void add(int x,int y){ go[++tot]=y; next[tot]=h[x]; h[x]=tot;}void dfs(int x,int y){ pp[x]=y; int t=h[x]; while (t){ if (go[t]!=y) dfs(go[t],x); t=next[t]; }}int pd(int x){ return tree[father[x]][1]==x;}void update(int x){ siz[x]=siz[tree[x][0]]^siz[tree[x][1]]^key[x]; num[x]=num[tree[x][0]]^num[tree[x][1]]^sum[x];}void rotate(int x){ int y=father[x],z=pd(x); father[x]=father[y]; if (father[y]) tree[father[y]][pd(y)]=x; tree[y][z]=tree[x][1-z]; if (tree[x][1-z]) father[tree[x][1-z]]=y; tree[x][1-z]=y; father[y]=x; update(y); update(x); if (pp[y]) pp[x]=pp[y],pp[y]=0;}void clear(int x){ if (bz[x]){ if (tree[x][0]) bz[tree[x][0]]^=1; if (tree[x][1]) bz[tree[x][1]]^=1; swap(tree[x][0],tree[x][1]); bz[x]=0; }}void remove(int x,int y){ top=0; while (x!=y){ sta[++top]=x; x=father[x]; } while (top){ clear(sta[top]); top--; }}void splay(int x,int y){ remove(x,y); while (father[x]!=y){ if (father[father[x]]!=y) if (pd(x)==pd(father[x])) rotate(father[x]);else rotate(x); rotate(x); }}int find_left(int x){ if (!x) return 0; clear(x); if (!tree[x][0]) return x; else return find_left(tree[x][0]);}int getnum(int x){ splay(x,0); return sum[x]^num[tree[x][1]]^siz[tree[x][1]]^key[x];}void real_empty(int x,int y){ int t=getnum(x); splay(y,0); splay(x,y); tree[y][1]=0; father[x]=0; pp[x]=y; sum[y]^=t; update(y);}void empty_real(int x,int y){ int t=getnum(x); splay(y,0); splay(x,0); tree[y][1]=x; father[x]=y; pp[x]=0; sum[y]^=t; update(y);}void access(int x){ int y,z; splay(x,0); z=find_left(tree[x][1]); if (z){ splay(z,x); real_empty(z,x); } while (pp[x]){ y=pp[x]; splay(y,0); z=find_left(tree[y][1]); if (z){ splay(z,y); real_empty(z,y); } splay(x,0); z=find_left(x); splay(z,0); empty_real(z,y); splay(x,0); }}void makeroot(int x){ access(x); splay(x,0); bz[x]^=1;}void cut(int x,int y){ makeroot(x); access(x); int t=getnum(y); splay(x,0); sum[x]^=t; update(x); splay(y,0); pp[y]=0;}void link(int x,int y){ makeroot(x); makeroot(y); int t=getnum(y); splay(x,0); sum[x]^=t; update(x); splay(y,0); pp[y]=x;}void insert(int p,int l,int r,int a,int b){ if (l==r){ size[p]+=b; return; } int mid=(l+r)/2; if (a<=mid) insert(p*2,l,mid,a,b);else insert(p*2+1,mid+1,r,a,b); size[p]=size[p*2]+size[p*2+1];}int kth(int p,int l,int r,int k){ if (l==r) return l; int mid=(l+r)/2; if (k<=size[p*2]) return kth(p*2,l,mid,k);else return kth(p*2+1,mid+1,r,k-size[p*2]);}int main(){ //freopen("data.in","r",stdin);freopen("data.out","w",stdout); srand(time(0)); id=read(); n=read();m=read(); fo(i,1,n-1){ j=read();k=read(); add(j,k);add(k,j); } dfs(1,0); tot=0; fo(i,1,m){ ask[i][0]=read(); ask[i][1]=read(); if (ask[i][0]!=3) ask[i][2]=read(); if (ask[i][0]==1) ask[i][3]=read(),ask[i][4]=read(); if (ask[i][0]==2) ask[i][3]=++tot,c[tot]=i; } fo(i,1,m){ if (ask[i][0]==1){ j=ask[i][1];k=ask[i][2];u=ask[i][3];v=ask[i][4]; cut(j,k); link(u,v); } else if (ask[i][0]==2){ insert(1,1,tot,ask[i][3],1); j=ask[i][1];k=ask[i][2]; b[ask[i][3]]=random(md)+1; access(j); splay(j,0); key[j]^=b[ask[i][3]]; update(j); access(k); splay(k,0); key[k]^=b[ask[i][3]]; update(k); wdc^=b[ask[i][3]]; } else if (ask[i][0]==3){ //t=kth(1,1,tot,ask[i][1]); t=ask[i][1]; insert(1,1,tot,t,-1); j=ask[c[t]][1];k=ask[c[t]][2]; access(j); splay(j,0); key[j]^=b[ask[c[t]][3]]; update(j); access(k); splay(k,0); key[k]^=b[ask[c[t]][3]]; update(k); wdc^=b[ask[c[t]][3]]; } else{ j=ask[i][1];k=ask[i][2]; cut(j,k); makeroot(j); ans=getnum(j); if (ans==wdc) PRintf("YES/n");else printf("NO/n"); link(j,k); } }}新闻热点
疑难解答
