又是因為傻逼錯誤浪費了半天時間

原題：

給定一棵N個節(jié)點的樹，每個點有一個權(quán)值，對于M個詢問(u,v,k)，你需要回答u xor lastans和v這兩個節(jié)點間第K小的點權(quán)。其中l(wèi)astans是上一個詢問的答案，初始為0，即第一個詢問的u是明文。 N,M<=100000 暴力自重。。。 樹上煮席樹，我和rapiz討論了一段時間覺得區(qū)間不連續(xù)咋做啊 然后去膜黃學(xué)長的代碼，順間get到正解（然后瞬間寫出程序，然后一個傻逼錯誤調(diào)了3h 在線段上搞煮席樹搞得是前綴和，樹上也可以搞一個樹上前綴和然后搞煮席樹 大概就是每個節(jié)點都在這個節(jié)點爸爸的基礎(chǔ)上修改一個新版本 設(shè)要查詢a和b，c=lca(a,b)，d=father(lca(a,b))，在煮席樹查詢的時候只需要比較sum(a.lchild)+sum(b.lchild)-sum(c.lchild)-sum(d.lchild)即可 注意d要是c的爸爸而不能直接c<<1，lca也要算進去 傻逼錯誤就是建樹的時候存的單項邊 實力真的越來越弱了 代碼： 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 int read(){int z=0,mark=1; char ch=getchar(); 8 while(ch<'0'||ch>'9'){if(ch=='-')mark=-1; ch=getchar();} 9 while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0'; ch=getchar();} 10 return z*mark; 11 } 12 struct ddd{int next,y;}e[210000]; int LINK[110000],ltop=0; 13 inline void insert(int x,int y){e[++ltop].next=LINK[x];LINK[x]=ltop;e[ltop].y=y;} 14 int n,m,a[110000]; int b[110000],disperse[110000],disperse_cnt=0; 15 int ancestor[110000][20],deep[110000]; 16 int dfs_order[110000],order_cnt=0; 17 struct dcd{int sleft,sright,mid,lchild,rchild,svalue;}tree[4100000]; 18 int roots[110000],tree_cnt=0; 19 int get_SegmentTree(int x,int _left,int _right){ 20 tree[x].sleft=_left,tree[x].sright=_right,tree[x].mid=(_left+_right)>>1; 21 tree[x].svalue=0; 22 if(_left!=_right){ 23 tree[x].lchild=get_SegmentTree(++tree_cnt,_left,tree[x].mid); 24 tree[x].rchild=get_SegmentTree(++tree_cnt,tree[x].mid+1,_right); 25 } 26 return x; 27 } 28 int modify(int x,int y){ 29 tree[++tree_cnt]=tree[x]; x=tree_cnt; tree[x].svalue++; 30 if(tree[x].sleft==y && tree[x].sright==y) return x; 31 if(y<=tree[x].mid) tree[x].lchild=modify(tree[x].lchild,y); 32 else tree[x].rchild=modify(tree[x].rchild,y); 33 return x; 34 } 35 /*int query(int x,int y,int z){ 36 if(tree[x].sleft==tree[x].sright) return tree[x].sleft; 37 else if(z<=tree[tree[y].lchild].svalue-tree[tree[x].lchild].svalue) 38 return query(tree[x].lchild,tree[y].lchild,z); 39 else return query(tree[x].rchild,tree[y].rchild, 40 z-tree[tree[x].lchild].svalue+tree[tree[x].lchild].svalue); 41 }*/ 42 int query(int x,int y,int z,int zz,int _value){ 43 if(tree[x].sleft==tree[x].sright) return tree[x].sleft; 44 int value_sum=tree[tree[x].lchild].svalue+tree[tree[y].lchild].svalue 45 -tree[tree[z].lchild].svalue-tree[tree[zz].lchild].svalue; 46 if(_value<=value_sum) return query(tree[x].lchild,tree[y].lchild,tree[z].lchild,tree[zz].lchild,_value); 47 else return query(tree[x].rchild,tree[y].rchild,tree[z].rchild,tree[zz].rchild,_value-value_sum); 48 } 49 int binary_search(int x){ 50 int _left=1,_right=disperse_cnt,mid; 51 while(_left+1<_right){ 52 mid=(_left+_right)>>1; 53 if(disperse[mid]<=x) _left=mid; 54 else _right=mid; 55 } 56 return (disperse[_right]==x)?_right:_left; 57 } 58 void dfs(int x){ 59 dfs_order[++order_cnt]=x; 60 for(int i=1;(1<<i)<=deep[x];++i) ancestor[x][i]=ancestor[ancestor[x][i-1]][i-1]; 61 for(int i=LINK[x];i;i=e[i].next)if(e[i].y!=ancestor[x][0]){ 62 ancestor[e[i].y][0]=x; deep[e[i].y]=deep[x]+1; 63 //roots[e[i].y]=modify(roots[x],binary_search(a[e[i].y])); 64 dfs(e[i].y); 65 } 66 } 67 int lca(int x,int y){ 68 if(deep[x]<deep[y]) swap(x,y); 69 int _deep=deep[x]-deep[y]; 70 for(int i=0;i<=16;++i)if((1<<i)&_deep) x=ancestor[x][i]; 71 for(int i=16;i>=0;--i)if(ancestor[x][i]!=ancestor[y][i]) 72 x=ancestor[x][i],y=ancestor[y][i]; 73 if(x==y) return x; 74 else return ancestor[x][0]; 75 } 76 int main(){//freopen("ddd.in","r",stdin); 77 cin>>n>>m; 78 for(int i=1;i<=n;++i) b[i]=a[i]=read(); 79 sort(b+1,b+n+1); 80 for(int i=1;i<=n;++i)if(b[i]!=b[i-1]) disperse[++disperse_cnt]=b[i]; 81 int _left,_right,_value; 82 for(int i=1;i<n;++i){ 83 _left=read(),_right=read(); 84 insert(_left,_right),insert(_right,_left); 85 } 86 roots[0]=get_SegmentTree(tree_cnt=0,1,disperse_cnt); 87 insert(0,1); 88 dfs(0); 89 for(int i=1;i<=order_cnt;++i){ 90 int temp=dfs_order[i]; 91 roots[temp]=modify(roots[ancestor[temp][0]],binary_search(a[temp])); 92 } 93 int last=0; 94 while(m --> 0){//趨向于 95 _left=read(),_right=read(),_value=read(); 96 _left^=last; 97 last=disperse[query(roots[_left],roots[_right], 98 roots[lca(_left,_right)],roots[ancestor[lca(_left,_right)][0]],_value)]; 99 printf("%d",last); 100 if(m) printf("\n"); 101 } 102 return 0; 103 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/JSL2018/p/6393165.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ2558】Count on a tree的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。