(题目链接)
题意
给出一棵无根树，4种操作：在路径集合中加入一条路径，在路径集合中删除一条路径，删一条边加一条边，查询一条边是否被集合中所有路径经过。
Solution
将路径端点同时异或上一个值，那么如果一条路径被经过，那么它的子树中点的异或和一定等于所有路径的异或和。
考虑如何用LCT维护这种可加减的子树信息。
对于询问，我们将询问的点access一下，那么它的所有虚儿子就是它在真实的树中的所有儿子了。
对于会使轻重边切换的操作：access,link,cut。注意同时更新虚儿子信息。
细节
link的时候，两端点都要makeroot，否则作为父亲的一点无法更新祖先的信息。
代码
#include#include #include #include #include #include #define LL long long#define inf (1ll<<30)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std; const int maxn=300010;int S,n,m,id,tot,fa[maxn]; struct edge {int u,v,w;}e[maxn];struct node { int son[2],val,sum,rev; //val=x+虚儿子;sum=val+实儿子 int& operator [] (int x) {return son[x];}}tr[maxn]; void reverse(int x) { swap(tr[x][0],tr[x][1]);tr[x].rev^=1;}void pushdown(int x) { if (tr[fa[x]][0]==x || tr[fa[x]][1]==x) pushdown(fa[x]); if (tr[x].rev) { if (tr[x][0]) reverse(tr[x][0]); if (tr[x][1]) reverse(tr[x][1]); tr[x].rev^=1; }}void pushup(int x) { tr[x].sum=tr[tr[x][0]].sum^tr[tr[x][1]].sum^tr[x].val;}void rotate(int x) { int y=fa[x],z=fa[y],l,r; l=tr[y][1]==x;r=l^1; if (tr[z][0]==y || tr[z][1]==y) tr[z][tr[z][1]==y]=x; fa[tr[x][r]]=y;fa[x]=z;fa[y]=x; tr[y][l]=tr[x][r];tr[x][r]=y; pushup(y);pushup(x);}void splay(int x) { pushdown(x); while (tr[fa[x]][0]==x || tr[fa[x]][1]==x) { int y=fa[x],z=fa[y]; if (tr[z][0]==y || tr[z][1]==y) { if ((tr[z][0]==y) ^ (tr[y][0]==x)) rotate(x); else rotate(y); } rotate(x); }}void access(int x) { for (int y=0;x;y=x,x=fa[x]) { splay(x);tr[x].val^=tr[tr[x][1]].sum; tr[x].val^=tr[tr[x][1]=y].sum; pushup(x); }}void makeroot(int x) { access(x);splay(x);reverse(x);}void link(int x,int y) { makeroot(x);makeroot(y); //一定要makeroot(y)，否则无法更新y所在的splay上祖先的信息 fa[x]=y;tr[y].val^=tr[x].sum; pushup(y);}void cut(int x,int y) { makeroot(x);access(y);splay(y); fa[x]=tr[y][0]=0;pushup(y);}void modify(int x,int val) { access(x);splay(x); tr[x].val^=val;tr[x].sum^=val;}bool query(int x,int y) { makeroot(x);access(y); //access以后，y在实树上的儿子全为它的虚儿子 return tr[y].val==S ? 1 : 0;} int main() { scanf("%d%d%d",&id,&n,&m); for (int x,y,i=1;i