给定一棵 \(n\) 个点的树，每个点上有位运算 \(opt\) 和一个权值 \(x\)，位运算有 &,|,^ 三种。
要求支持：
修改点 \(v\) 的 \(opt\) 和 \(x_v\)
确定一个初始点权在 \([0,z]\) 之间的 \(v_0\)，然后依次经过从 \(x\) 到 \(y\) 的所有节点。每经过一个节点 \(i\)， \(v\) 就变成 \(v\;opt\;x_i\) 请回答最后到 \(y\) 时可能的最大的 \(v\) 。
Solution首先五十分的做法比较显然，就是拆位建 \(lct\)，然后每位分开做，复杂度 \(O(nk\log n)\)。
这样只有 \(50\) 分，考虑优化复杂度。
因为 \(O(n\log n)\) 已经是 \(lct\) 的复杂度了不是很能优化掉，考虑去掉复杂度乘上的 \(k\)。
有这个 \(k\) 的原因是我们对于每一位都搞了棵 \(lct\) 出来。如果我们只弄一棵 \(lct\) 是否可行呢？
定义 \(f0,f1\) 分别为初始值全 \(0/1\) 走过一条路径之后的答案
那在 \(lct\) 中需要维护的就是 \(splay\) 里 \(x\) 的子树，中序遍历的 \(f0,f1\) 已经倒着的中序遍历（与中序遍历相反）\(f0,f1\) （要维护这个倒着的原因是当前点 \(x\) 的值与左右子树的顺序有关，而 \(splay\) 中又有 \(reverse\) 操作所以要维护）。
那有了这个能不能快速更新呢？也就是说有左区间的 \(f0,f1\) 和右区间的 \(g0,g1\)，能不能快速求出来 \(h0,h1\) 呢？废话
更新式子比较显然就是：\(h0=(f0\&g1)+(\sim f0\& g0),h1=(f1\And g1)+(\sim f1\& g0)\)
证明的话就是全 \(0\) 放进去左区间之后跑出来的是 \(f0\)，可能长 \(10010001010\) 这样，然后再去 $\And $ 一下 \(g1\) 就代表这些当前为 \(1\) 的位放进右区间之后跑出来的是多少。因为 \(\&\) 了 \(f0\) 所以最后答案肯定不会比 \(f0\) 大。其它几项的证明也类似就不去证了。
最后求出来 从 \(x\) 到 \(y\) 的 \(f0,f1\) 之后贪心的选就好了。
Code #include<set> #include<map> #include<cmath> #include<queue> #include<cctype> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using std::min; using std::max; using std::swap; using std::vector; typedef double db; typedef unsigned long long ll; #define pb(A) push_back(A) #define pii std::pair<int,int> #define all(A) A.begin(),A.end() #define mp(A,B) std::make_pair(A,B) namespace NewweN{ const int N=1e5+5; int n,m,cnt,head[N],stk[N],top; int fa[N],ch[N][2],tag[N],k;ll maxn; char buf[1048578];int ptr,MX; #define ls ch[x][0] #define rs ch[x][1] struct Edge{ int to,nxt; }edge[N<<1]; void add(int x,int y){ edge[++cnt].to=y; edge[cnt].nxt=head[x]; head[x]=cnt; } struct Node{ ll a,b; Node(){} Node(ll x,ll y){ a=x,b=y; } friend Node operator+(Node x,Node y){ return Node((x.a&y.b)+(((~x.a))&y.a),(x.b&y.b)+(((~x.b))&y.a)); } }l[N],r[N],val[N]; char nc(){ if(ptr==MX) MX=fread(buf,1,1<<20,stdin),ptr=0; return ptr==MX?EOF:buf[ptr++]; } #define getchar nc ll getint(){ ll X=0,w=0;char ch=getchar(); while(!isdigit(ch))w|=ch=='-',ch=getchar(); while( isdigit(ch))X=X*10+ch-48,ch=getchar(); if(w) return -X;return X; } void dfs(int now,int f=0){ for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(to==f)continue; fa[to]=now; dfs(to,now); } } void pushup(int x){ l[x]=r[x]=val[x]; if(ls)l[x]=l[ls]+l[x],r[x]=r[x]+r[ls]; if(rs)l[x]=l[x]+l[rs],r[x]=r[rs]+r[x]; } void pushr(int x){ tag[x]^=1;swap(ls,rs);swap(l[x],r[x]); } void pushdown(int x){ if(tag[x])tag[x]=0,pushr(ls),pushr(rs); } bool nroot(int x){ return ch[fa[x]][0]==x or ch[fa[x]][1]==x; } void rotate(int x){ int y=fa[x],z=fa[y],d=ch[y][1]==x,dd=ch[z][1]==y; ch[y][d]=ch[x][d^1];if(ch[x][d^1])fa[ch[x][d^1]]=y; fa[x]=z;if(nroot(y))ch[z][dd]=x; fa[y]=x;ch[x][d^1]=y;pushup(y); } void splay(int x){ int now=x;stk[++top]=now; while(nroot(now))now=fa[now],stk[++top]=now; while(top)pushdown(stk[top--]); while(nroot(x)){ int y=fa[x],z=fa[y]; if(nroot(y))rotate((ch[y][1]==x)^(ch[z][1]==y)?x:y); rotate(x); }pushup(x); } void access(int x){ for(int y=0;x;y=x,x=fa[x]){ splay(x);rs=y; pushup(x); } } void makeroot(int x){ access(x),splay(x),pushr(x); } void split(int x,int y){ makeroot(x),access(y),splay(y); } signed main(){ n=getint(),m=getint(),k=getint(); maxn=(1ull<<k)-1; for(int i=1;i<=n;i++){ ll x=getint(),y=getint(); if(x==1)val[i]=Node(0,y); if(x==2)val[i]=Node(y,~0); if(x==3)val[i]=Node(y,(~y)); } for(int i=1;i<n;i++){ int x=getint(),y=getint(); add(x,y),add(y,x); } dfs(1); while(m--){ int opt=getint(),x=getint(),y=getint();ll z=getint(); if(opt==1){ split(x,y); ll ans=0,used=0; for(int i=k-1;~i;i--){ if(l[y].a>>i&1ull) ans|=1ull<<i; else if((l[y].b>>i&1ull) and (used|(1ull<<i))<=z) ans|=1ull<<i,used|=1ull<<i; } printf("%llu\n",ans); } else{ splay(x); if(y==1) val[x]=Node(0,z); if(y==2) val[x]=Node(z,~0); if(y==3) val[x]=Node(z,(~z)); pushup(x); } } return 0; } } int yzh=NewweN::main(); signed main(){return 0;}