网站建设 风险说明书,微信小程序获取wordpress文章,免费wordpress申请,WordPress使用固定连接挺不错的一道数据结构题QWQ。 一开始发现这个题如果不看数据范围的话#xff0c;妥妥的树上莫队啊23333#xff0c;然鹅10组数据是不可能让你舒舒服服的树上莫队卡过的23333 于是想了想#xff0c;这个题的模型就是#xff0c;把u到v链上的权值出现奇偶次的01串搞出来… 挺不错的一道数据结构题QWQ。 一开始发现这个题如果不看数据范围的话妥妥的树上莫队啊23333然鹅10组数据是不可能让你舒舒服服的树上莫队卡过的23333 于是想了想这个题的模型就是把u到v链上的权值出现奇偶次的01串搞出来然后第一个0的位置就是所求。。。。。 但是这个01串并不是很好搞因为每一位都得异或啊。。。。这样复杂度就要乘上一个 200000/32了(bitset压位)还不如树上莫队呢QWQ 不过有一种套路叫做hash异或我们就给每一个权值随机一个unsined long long范围的hash值大概率保证询问涉及的子集的异或和不为0(这个主要看人品了。。。因为总的来说肯定会有很多子集的异或和为0但是因为子集总数太过庞大询问涉及的只是小部分所以出错概率还是很小的2333) 这样如果一个区间所有数都出现奇数次那么区间的hash异或起来就和 路径权值线段树在这个区间异或起来的值一样了直接在主席树上二分即可。。。 (注意lca是要被算上的但是如果直接用到根前缀的两个主席树异或的话lca是会被消去的) #includebits/stdc.h
#define ll unsigned long long
using namespace std;
const int maxn200005;
#define mid (lr1)
int T,n,a[maxn],m,to[maxn*2],ne[maxn*2],dep[maxn],le,w,A,B,ans;
int hd[maxn],num,siz[maxn],son[maxn],cl[maxn],f[maxn],ri,lca;
inline void add(int x,int y){ to[num]y,ne[num]hd[x],hd[x]num;}
ll val[maxn],Xor[maxn],now;
struct node{ll sum;node *lc,*rc;
}nil[maxn*37],*rot[maxn],*cnt;inline void init(){nil-sum0;nil-lcnil-rcrot[0]cntnil;fill(hd1,hdn1,0),num0;memset(son,0,sizeof(son));
}node *update(node *u,int l,int r){node *retcnt;*ret*u,ret-sum^val[le];if(lr) return ret;if(lemid) ret-lcupdate(ret-lc,l,mid);else ret-rcupdate(ret-rc,mid1,r);return ret;
}void query(node *u,int l,int r){if(llerri){ now^u-sum; return;}if(lemid) query(u-lc,l,mid);if(rimid) query(u-rc,mid1,r);
}void Fdfs(int x,int fa){f[x]fa,siz[x]1,dep[x]dep[fa]1;lea[x],rot[x]update(rot[fa],1,200001);for(int ihd[x];i;ine[i]) if(to[i]!fa){Fdfs(to[i],x),siz[x]siz[to[i]];if(!son[x]||siz[to[i]]siz[son[x]]) son[x]to[i];}
}void Sdfs(int x,int tp){cl[x]tp;if(!son[x]) return;Sdfs(son[x],tp);for(int ihd[x];i;ine[i]) if(to[i]!f[x]to[i]!son[x]) Sdfs(to[i],to[i]);
}int LCA(int x,int y){while(cl[x]!cl[y]){if(dep[cl[x]]dep[cl[y]]) xf[cl[x]];else yf[cl[y]];}return dep[x]dep[y]?x:y;
}void query(node *u,node *v,int l,int r){if(lr){ ansl; return;}if((u-lc-sum^v-lc-sum^((a[lca]la[lca]mid)?val[a[lca]]:0))(Xor[mid]^Xor[l-1])) query(u-rc,v-rc,mid1,r);else query(u-lc,v-lc,l,mid);
}inline void solve(){Fdfs(1,0),Sdfs(1,1);while(m--){scanf(%d%d,A,B),lcaLCA(A,B);query(rot[A],rot[B],1,200001);printf(%d\n,ans);}
}int main(){
// freopen(data.in,r,stdin);
// freopen(data.out,w,stdout);val[1]1;for(int i2;i200001;i) val[i]val[i-1]*233ll;for(int i1;i200001;i) Xor[i]val[i]^Xor[i-1];scanf(%d,T);while(T--){init(),scanf(%d%d,n,m);for(int i1;in;i) scanf(%d,ai);int uu,vv;for(int i1;in;i) scanf(%d%d,uu,vv),add(uu,vv),add(vv,uu);solve();}return 0;
}转载于:https://www.cnblogs.com/JYYHH/p/9099254.html
