首页 > 代码库 > UOJ 274 【清华集训2016】温暖会指引我们前行 ——Link-Cut Tree
UOJ 274 【清华集训2016】温暖会指引我们前行 ——Link-Cut Tree
魔法森林高清重置,
只需要维护关于t的最大生成树,然后链上边权求和即可。
直接上LCT
调了将近2h
吃枣药丸
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i) #define maxn 1000005 #define inf 0x3f3f3f3f struct Link_Cut_Tree{ int ch[maxn][2],fa[maxn],rev[maxn],mn[maxn],val[maxn],sum[maxn],len[maxn]; int sta[maxn],top; bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;} void update(int x) { mn[x]=x; if (val[mn[ch[x][0]]]<val[mn[x]]) mn[x]=mn[ch[x][0]]; if (val[mn[ch[x][1]]]<val[mn[x]]) mn[x]=mn[ch[x][1]]; sum[x]=len[x]+sum[ch[x][0]]+sum[ch[x][1]]; } void pushdown (int x) { if (rev[x]) { rev[x]^=1; rev[ch[x][0]]^=1; rev[ch[x][1]]^=1; swap(ch[x][0],ch[x][1]); } } void rot(int x) { int y=fa[x],z=fa[y],l,r; if (ch[y][0]==x) l=0; else l=1; r=l^1; if (!isroot(y)) { if (ch[z][0]==y) ch[z][0]=x; else ch[z][1]=x; } fa[x]=z; fa[y]=x; fa[ch[x][r]]=y; ch[y][l]=ch[x][r]; ch[x][r]=y; update(y);update(x); } void splay(int x) { top=0;sta[++top]=x; for (int i=x;!isroot(i);i=fa[i]) sta[++top]=fa[i]; while (top) pushdown(sta[top--]); while (!isroot(x)) { int y=fa[x],z=fa[y]; if (!isroot(y)) { if (ch[z][0]==y^ch[y][0]==x) rot(x); else rot(y); } rot(x); } } void access(int x) { for (int t=0;x;t=x,x=fa[x]) splay(x),ch[x][1]=t,update(x); } void makeroot(int x) { access(x); splay(x); rev[x]^=1; } int find(int x) { access(x); splay(x); while (ch[x][0]) x=ch[x][0]; return x; } void link(int x,int y) { makeroot(x); fa[x]=y; } void cut(int x,int y) { makeroot(x); access(y); ch[y][0]=0; fa[x]=0; } int query(int x,int y) { if (find(x)!=find(y)) return -1; makeroot(x);access(y);splay(y); return sum[y]; } int qmn(int x,int y) { makeroot(x);access(y);splay(y); return mn[y]; } void modify(int x,int l) { access(x);splay(x); len[x]=l;update(x); } }LCT; int n,m,u[maxn],v[maxn],id,t,l,x,y,in[maxn]; char opt[11]; int main() { scanf("%d%d",&n,&m); F(i,0,n) LCT.val[i]=inf; F(i,1,m) { scanf("%s",opt); switch(opt[0]) { case ‘f‘: scanf("%d",&id); id++; scanf("%d%d%d%d",&u[id],&v[id],&t,&l);u[id]++;v[id]++; LCT.len[id+n]=l;LCT.val[id+n]=t;LCT.mn[id+n]=id+n; if (LCT.find(u[id])!=LCT.find(v[id])) { LCT.link(id+n,u[id]); LCT.link(id+n,v[id]); in[id]=1; } else { int tmp=LCT.qmn(u[id],v[id]); if (LCT.val[tmp]<t) { LCT.cut(u[tmp-n],tmp); LCT.cut(v[tmp-n],tmp); in[tmp-n]=0; LCT.link(id+n,u[id]); LCT.link(id+n,v[id]); in[id]=1; } } break; case ‘m‘: scanf("%d%d",&x,&y);x++;y++; printf("%d\n",LCT.query(x,y)); break; case ‘c‘: scanf("%d%d",&id,&l); id++; if (in[id]) LCT.modify(id+n,l); break; } } }
UOJ 274 【清华集训2016】温暖会指引我们前行 ——Link-Cut Tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。