




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、LCT link-cut-tree 動(dòng)態(tài)樹模版題合集by yusitongBzoj 2049加邊、刪邊、查詢所在聯(lián)通塊/*Problem: 2049User: yusitongLanguage: C+Result: AcceptedTime:2036 msMemory:988 kb*/#include#include#includeusing namespace std;const int INF=0x7fffffff;const int N = 11000;int n,m;int faN,chN2;bool revN;int staN,top;bool isroot(int x)return
2、 chfax0!=x&chfax1!=x;void down(int x)if(!revx)return;revchx0=1;revchx1=1;swap(chx0,chx1);revx=0;void rotate(int x,int f)int y=fax;if(!isroot(y)chfaychfay1=y=x;fax=fay;if(chxf)fachxf=y;chy!f=chxf;fay=x;chxf=y;void splay(int x)sta+top=x;for(int i=x;!isroot(i);i=fai)sta+top=fai;while(top)down(statop-);
3、while(!isroot(x)if(!isroot(fax)if(chfax1=x)(chfafax1=fax)rotate(x,chfax0=x);else rotate(fax,chfafax0=fax);rotate(x,chfax0=x);void access(int x)int t=0;while(x)splay(x);chx1=t;t=x;x=fax;void makeroot(int x)access(x);splay(x);revx=1;void link(int x,int y)makeroot(x);fax=y;splay(x);void cut(int x,int y
4、)makeroot(x);access(y);splay(y);fax=0;chy0=0;int find(int x)access(x);splay(x);while(chx0)x=chx0;return x;int main()scanf(%d%d,&n,&m);char op10;int x,y;for(int i=1;i=m;i+)scanf(%s%d%d,op,&x,&y);if(op0=C)link(x,y);else if(op0=D)cut(x,y);elseputs(find(x)=find(y)?Yes:No);return 0;Bzoj2002 加邊、刪邊、查詢到根的距離
5、/*Problem: 2002User: yusitongLanguage: C+Result: AcceptedTime:2192 msMemory:5712 kb*/#include#include#includeusing namespace std;const int INF=0x7fffffff;const int N = 201000;int n,m;int faN,chN2,sizeN;bool revN;int nxtN;int staN,top;bool isroot(int x)return chfax0!=x&chfax1!=x;void up(int x)sizex=s
6、izechx0+sizechx1+1;void down(int x)if(!revx)return;revchx0=1;revchx1=1;revx=0;swap(chx0,chx1);void rotate(int x,int f)int y=fax;if(!isroot(y)chfaychfay1=y=x;fax=fay;if(chxf)fachxf=y;chy!f=chxf;fay=x;chxf=y;up(y);void splay(int x)sta+top=x;for(int i=x;!isroot(i);i=fai)sta+top=fai;while(top)down(stato
7、p-);while(!isroot(x)if(!isroot(fax)if(chfax0=x)(chfafax0=fax)rotate(x,chfax0=x);else rotate(fax,chfafax0=fax);rotate(x,chfax0=x);up(x);void access(int x)int t=0;while(x)splay(x);chx1=t;/ up(x);/?t=x;x=fax;void makeroot(int x)access(x);splay(x);revx=1;void link(int x,int y)makeroot(x);fax=y;splay(x);
8、void cut(int x,int y)makeroot(x);access(y);splay(y);fax=0;chy0=0;/up?int main()scanf(%d,&n);for(int i=1,t;i=n;i+) scanf(%d,&t);t=min(i+t,n+1);fai=nxti=t;sizei=1;sizen+1=1;scanf(%d,&m);int op,x,y;for(int i=1;i=m;i+)scanf(%d%d,&op,&x);x+;if(op=1)makeroot(n+1);access(x);splay(x);printf(%dn,sizechx0); e
9、lsescanf(%d,&y);y=min(x+y,n+1);cut(x,nxtx);link(x,y);nxtx=y;return 0;Bzoj 3282加邊、刪邊、單點(diǎn)修改,樹鏈查詢#include#include#includeusing namespace std;const int INF=0x7fffffff;const int N = 301000;int n,m;int faN,chN2,sizeN,valN,xsumN;bool revN;int staN,top;#define rep(i,l,r) for(int i=(l);i9|t=0&t=9)x=x*10+t-0,t
10、=getchar();return x*f;bool isroot(int x)return chfax0!=x&chfax1!=x;void up(int x)int l=chx0,r=chx1;xsumx=xsumlxsumrvalx;sizex=sizel+sizer+1;void down(int x)if(!revx)return;revchx0=1;revchx1=1;revx=0;swap(chx0,chx1);void rotate(int x,int f)int y=fax;if(!isroot(y)chfaychfay1=y=x;fax=fay;if(chxf)fachxf
11、=y;chy!f=chxf;fay=x;chxf=y;up(y);void splay(int x)sta+top=x;for(int i=x;!isroot(i);i=fai)sta+top=fai;while(top)down(statop-);while(!isroot(x)if(!isroot(fax)if(chfax0=x)(chfafax0=fax)rotate(x,chfax0=x);else rotate(fax,chfafax0=fax);rotate(x,chfax0=x);up(x);void access(int x)int t=0;while(x)splay(x);c
12、hx1=t;up(x);t=x;x=fax;void makeroot(int x)access(x);splay(x);revx=1;void split(int x,int y)makeroot(x);access(y);splay(y);void link(int x,int y)makeroot(x);fax=y;void cut(int x,int y)makeroot(x);access(y);splay(y);chy0=0;fax=0;up(y);int find(int x)access(x);splay(x);while(chx0)x=chx0;return x;int main()n=read();m=read();rep(i,1,n)xsumi=vali=read();sizei=1;int op,x,y;rep(i,1,m)op=read();x=read();y=read();if(op=0)split(x,y);printf(%dn,xsumy);else if(op=1)if(find(x)!=find(y)link(x,y);else if(op=2)if(find(x)=find(y)cut(x,y);elsemakeroot(x);xsumx=xsumxvalx
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年度防火門研發(fā)生產(chǎn)項(xiàng)目合同范本
- 2025年度防盜門企業(yè)社會(huì)責(zé)任與可持續(xù)發(fā)展合作協(xié)議
- 2025年度車輛改裝設(shè)計(jì)與定制合同
- 2025高空作業(yè)車租賃及高空作業(yè)人員資質(zhì)認(rèn)證合同
- 2025年度汽車租賃合同掛靠車輛租賃價(jià)格調(diào)整協(xié)議4篇
- 2025年度一次性網(wǎng)絡(luò)安全服務(wù)合同1(數(shù)據(jù)安全防護(hù))
- 2025年獨(dú)立運(yùn)行風(fēng)力發(fā)電機(jī)組控制器及逆變器項(xiàng)目發(fā)展計(jì)劃
- 優(yōu)化前臺(tái)服務(wù)流程的工作計(jì)劃
- 開展公益活動(dòng)的經(jīng)驗(yàn)與總結(jié)計(jì)劃
- 保安工作計(jì)劃收藏業(yè)古董收藏部門
- 小紅書文旅營(yíng)銷CityWalk城市漫游(通案)
- 寒假生活回顧分享小學(xué)主題班會(huì) 課件
- 湖南省長(zhǎng)沙市2024-2025學(xué)年高一數(shù)學(xué)上學(xué)期期末考試試卷
- 2024-2025學(xué)年上外版高二上學(xué)期期中英語(yǔ)試卷與參考答案
- 《學(xué)習(xí)地圖》課件
- 抓住人工智能科學(xué)機(jī)遇 A new golden age of discovery Seizing the AI for Science opportunity 2024
- 松材線蟲調(diào)查培訓(xùn)
- 方志敏《可愛(ài)的中國(guó)》全文閱讀
- 2024年廣西區(qū)公務(wù)員錄用考試《行測(cè)》真題及答案解析
- 《地區(qū)智能電網(wǎng)調(diào)度技術(shù)支持系統(tǒng)應(yīng)用功能規(guī)范》
- 框架借款協(xié)議書(2篇)
評(píng)論
0/150
提交評(píng)論