?

??? 挺不錯的一道數據結構題QWQ。

??? 一開始發現這個題如果不看數據范圍的話，妥妥的樹上莫隊啊23333，然鵝10組數據是不可能讓你舒舒服服的樹上莫隊卡過的23333

??? 于是想了想，這個題的模型就是，把u到v鏈上的權值出現奇偶次的01串搞出來，然后第一個0的位置就是所求。。。。。

??? 但是這個01串并不是很好搞，因為每一位都得異或啊。。。。這樣復雜度就要乘上一個 200000/32了(bitset壓位)，還不如樹上莫隊呢QWQ

?

??? 不過有一種套路，叫做hash異或，我們就給每一個權值隨機一個unsined long long范圍的hash值，大概率保證詢問涉及的子集的異或和不為0(這個主要看人品了。。。因為總的來說肯定會有很多子集的異或和為0，但是因為子集總數太過龐大，詢問涉及的只是小部分，所以出錯概率還是很小的2333)

?

??? 這樣，如果一個區間所有數都出現奇數次，那么區間的hash異或起來就和 路徑權值線段樹在這個區間異或起來的值一樣了，直接在主席樹上二分即可。。。

??? (注意lca是要被算上的，但是如果直接用到根前綴的兩個主席樹異或的話lca是會被消去的)

?

#include<bits/stdc++.h> #define ll unsigned long long using namespace std; const int maxn=200005; #define mid (l+r>>1) 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->sum=0;nil->lc=nil->rc=rot[0]=cnt=nil;fill(hd+1,hd+n+1,0),num=0;memset(son,0,sizeof(son)); }node *update(node *u,int l,int r){node *ret=++cnt;*ret=*u,ret->sum^=val[le];if(l==r) return ret;if(le<=mid) ret->lc=update(ret->lc,l,mid);else ret->rc=update(ret->rc,mid+1,r);return ret; }void query(node *u,int l,int r){if(l>=le&&r<=ri){ now^=u->sum; return;}if(le<=mid) query(u->lc,l,mid);if(ri>mid) query(u->rc,mid+1,r); }void Fdfs(int x,int fa){f[x]=fa,siz[x]=1,dep[x]=dep[fa]+1;le=a[x],rot[x]=update(rot[fa],1,200001);for(int i=hd[x];i;i=ne[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 i=hd[x];i;i=ne[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]]) x=f[cl[x]];else y=f[cl[y]];}return dep[x]<dep[y]?x:y; }void query(node *u,node *v,int l,int r){if(l==r){ ans=l; return;}if((u->lc->sum^v->lc->sum^((a[lca]>=l&&a[lca]<=mid)?val[a[lca]]:0))==(Xor[mid]^Xor[l-1])) query(u->rc,v->rc,mid+1,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),lca=LCA(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 i=2;i<=200001;i++) val[i]=val[i-1]*233ll;for(int i=1;i<=200001;i++) Xor[i]=val[i]^Xor[i-1];scanf("%d",&T);while(T--){init(),scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",a+i);int uu,vv;for(int i=1;i<n;i++) scanf("%d%d",&uu,&vv),add(uu,vv),add(vv,uu);solve();}return 0; }

?

轉載于:https://www.cnblogs.com/JYYHH/p/9099254.html

總結

以上是生活随笔為你收集整理的[Lydsy1805月赛] 对称数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。