深圳做网站哪家公司最好,北堂网站制作,莱芜雪野湖国际会议中心酒店,wordpress手机底部考虑到路径是有向的#xff0c;不是很好维护。 如果路径无向的话#xff0c;可以直接转化为链加和查询操作。 既然有向的话#xff0c;不妨考虑一波hash。 对于一组询问x,y#xff0c;可以把树划分为两颗子树。 合法显然需要满足 x子树的起点的hashy子树的终点的hash x子树…考虑到路径是有向的不是很好维护。 如果路径无向的话可以直接转化为链加和查询操作。 既然有向的话不妨考虑一波hash。 对于一组询问x,y可以把树划分为两颗子树。 合法显然需要满足 x子树的起点的hashy子树的终点的hash x子树的终点的hashy子树的起点的hash 直接用LCT维护一个异或hash即可。 #includeiostream
#includecctype
#includecstdio
#includecstring
#includestring
#includecmath
#includectime
#includecstdlib
#includealgorithm
#define N 330000
#define L 300000
#define eps 1e-7
#define inf 1e97
#define db double
#define ll long long
#define ldb long double
using namespace std;
inline int read()
{char ch0;int x0,flag1;while(!isdigit(ch)){chgetchar();if(ch-)flag-1;}while(isdigit(ch)){x(x3)(x1)ch-0;chgetchar();}return x*flag;
}
#define lson son[x][0]
#define rson son[x][1]
struct lnk{int x,y,z;}p[N];
int va[N],vb[N],sa[N],sb[N],sa_[N],sb_[N],f[N],st[N],flag[N],son[N][2];
bool get(int x){return son[f[x]][1]x;}
bool isroot(int x){return (son[f[x]][0]!x)(son[f[x]][1]!x);}
void pushup(int x)
{sa[x]sa[lson]^sa[rson]^sa_[x]^va[x];sb[x]sb[lson]^sb[rson]^sb_[x]^vb[x];
}
void update(int x){flag[x]^1;swap(lson,rson);}
void pushdown(int x){if(!flag[x])return;if(lson)update(lson);if(rson)update(rson);flag[x]0;}
void rotate(int x)
{int yf[x],zf[y],txget(x),tyget(y),pson[x][!tx];if(!isroot(y))son[z][ty]x;son[x][!tx]y;son[y][tx]p;if(p)f[p]y;f[y]x;f[x]z;pushup(y);pushup(x);
}
void splay(int x)
{int cnt0,tmpx;st[cnt]x;while(!isroot(x))st[cnt]f[x],xf[x];for(int icnt;i1;i--)pushdown(st[i]);xtmp;while(!isroot(x)){int yf[x];if(!isroot(y))rotate(get(x)get(y)?y:x);rotate(x);}pushup(x);
}
void access(int x)
{for(int y0;x;yx,xf[x]){splay(x);sa_[x]^sa[rson];sb_[x]^sb[rson];rsony;sa_[x]^sa[rson];sb_[x]^sb[rson];pushup(x);}
}
void makeroot(int x){access(x);splay(x);update(x);}
void link(int x,int y)
{makeroot(x);access(y);splay(y);f[x]y;sa_[y]^sa[x];sb_[y]^sb[x];pushup(y);
}
void cut(int x,int y)
{makeroot(x);access(y);splay(y);f[x]son[y][0]0;pushup(y);
}
void add1(int x,int k){makeroot(x);va[x]^k;pushup(x);}
void add2(int x,int k){makeroot(x);vb[x]^k;pushup(x);}
int rng(){int x0;for(int i0;i30;i)x^(rand()%2)i;return x;}
int main()
{srand(time(0));read();int nread(),mread(),cnt0,s0;for(int i1;in;i){int xread(),yread();link(x,y);}for(int i1;im;i){int flagread();if(flag1){int x,y;xread();yread();cut(x,y);xread();yread();link(x,y);}if(flag2){cnt;p[cnt].xread();p[cnt].yread();p[cnt].zrng();add1(p[cnt].x,p[cnt].z);add2(p[cnt].y,p[cnt].z);s^p[cnt].z;}if(flag3){int kread();add1(p[k].x,p[k].z);add2(p[k].y,p[k].z);s^p[k].z;}if(flag4){int xread(),yread();makeroot(x);access(y);int asa_[y]^va[y],bsb_[y]^vb[y]; if((a^b)s)printf(YES\n);else printf(NO\n);}}return 0;
} 转载于:https://www.cnblogs.com/Creed-qwq/p/10354399.html
