关键词:
鉴于最近写bzoj还有51nod都出现写不动的现象,决定学习一波厉害的算法/数据结构。
link cut tree:研究popoqqq那个神ppt。
bzoj1036:维护access操作就可以了。
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #include<queue> using namespace std; #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define clr(x,c) memset(x,c,sizeof(x)) #define qwq(x) for(edge *o=head[x];o;o=o->next) int read(){ int x=0,f=1;char c=getchar(); while(!isdigit(c)){ if(c==‘-‘) f=-1;c=getchar(); } while(isdigit(c)) x=x*10+c-‘0‘,c=getchar(); return x*f; } const int nmax=3e4+5; const int inf=0x7f7f7f7f; struct edge{ int to;edge *next; }; edge es[nmax<<1],*pt=es,*head[nmax]; void add(int u,int v){ pt->to=v;pt->next=head[u];head[u]=pt++; pt->to=u;pt->next=head[v];head[v]=pt++; } int n,m,fa[nmax],c[nmax][2],sm[nmax],mx[nmax],q[nmax],w[nmax];bool vis[nmax]; void bfs(){ int l=1,r=1,x;q[r]=1;vis[1]=1; while(l<=r){ x=q[l++]; qwq(x) if(!vis[o->to]) fa[o->to]=x,q[++r]=o->to,vis[o->to]=1; } } bool pdrt(int x){ return c[fa[x]][0]!=x&&c[fa[x]][1]!=x; } void update(int x){ int l=c[x][0],r=c[x][1]; sm[x]=sm[l]+sm[r]+w[x];mx[x]=max(w[x],max(mx[l],mx[r])); } void rotate(int x){ int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; if(!pdrt(y)) if(c[z][0]==y) c[z][0]=x;else c[z][1]=x; fa[x]=z;fa[y]=x;fa[c[x][r]]=y; c[y][l]=c[x][r];c[x][r]=y; update(y);update(x); } void splay(int x){ //把一个点伸展到它所在的重链的根。 int y,z;//fa[x]=y表示以x为根的splay树的父亲是y,但是y的两个儿子(c[y][0]和c[y][1])中没有一个是x while(!pdrt(x)){ y=fa[x];z=fa[y]; if(!pdrt(y)) if(c[y][0]==x^c[z][0]==y) rotate(x);else rotate(y); rotate(x); } } int access(int x){ int t=0; while(x) splay(x),c[x][1]=t,t=x,update(x),x=fa[x]; return t; //考虑点u,v。假设先access(u)了,那么access(lca(u,v))时lca(u,v)是原splay的根节点, //左边的是深度比它小的点,即是lca(u,v)到根的链。 说明access的操作是正确的。 } void qsum(int u,int v){ access(u);int lca=access(v);splay(u); if(lca==u) printf("%d ",w[u]+sm[c[lca][1]]); else printf("%d ",w[lca]+sm[c[lca][1]]+sm[u]); } void qmax(int u,int v){ access(u);int lca=access(v);splay(u); if(lca==u) printf("%d ",max(w[u],mx[c[lca][1]])); else printf("%d ",max(w[lca],max(mx[c[lca][1]],mx[u]))); } int main(){ n=read();int u,v,d;mx[0]=-inf; rep(i,1,n-1) u=read(),v=read(),add(u,v); rep(i,1,n) sm[i]=mx[i]=w[i]=read();bfs(); m=read();char ch[11]; rep(i,1,m){ scanf("%s",ch);u=read(),v=read(); if(ch[1]==‘H‘) splay(u),w[u]=v,update(u); else if(ch[1]==‘S‘) qsum(u,v); else qmax(u,v); } return 0; }
bzoj2049:link cut tree 模版题。
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define clr(x,c) memset(x,c,sizeof(x)) #define qwq(x) for(edge *o=head[x];o;o=o->next) int read(){ int x=0,f=1;char c=getchar(); while(!isdigit(c)){ if(c==‘-‘) f=-1;c=getchar(); } while(isdigit(c)) x=x*10+c-‘0‘,c=getchar(); return x*f; } const int nmax=1e4+5; int n,m,fa[nmax],c[nmax][2],st[nmax],rev[nmax]; bool pdrt(int x){ return c[fa[x]][0]!=x&&c[fa[x]][1]!=x; } void pushdown(int x){ if(rev[x]){ int l=c[x][0],r=c[x][1]; rev[x]^=1;rev[l]^=1;rev[r]^=1; swap(c[x][0],c[x][1]); } } void rotate(int x){ int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; if(!pdrt(y)) if(c[z][0]==y) c[z][0]=x;else c[z][1]=x; fa[x]=z;fa[y]=x;fa[c[x][r]]=y; c[y][l]=c[x][r];c[x][r]=y; } void splay(int x){ int top=0,y,z;st[++top]=x; for(int i=x;!pdrt(i);i=fa[i]) st[++top]=fa[i]; dwn(i,top,1) pushdown(st[i]); while(!pdrt(x)){ y=fa[x];z=fa[y]; if(!pdrt(y)) if(c[y][0]==x^c[z][0]==y) rotate(x);else rotate(y); rotate(x); } } void access(int x){ int t=0; while(x) splay(x),c[x][1]=t,t=x,x=fa[x]; } void rever(int x){ access(x);splay(x);rev[x]^=1; } void link(int x,int y){ rever(x);fa[x]=y; } void cut(int x,int y){ rever(x);access(y);splay(y);c[y][0]=fa[x]=0; } int find(int x){ access(x);splay(x); int y=x;while(c[y][0]) y=c[y][0]; return y; } int main(){ n=read(),m=read();int x,y;char ch[11]; rep(i,1,m){ scanf("%s",ch);x=read(),y=read(); if(ch[0]==‘C‘) link(x,y); else if(ch[0]==‘D‘) cut(x,y); else { if(find(x)==find(y)) puts("Yes"); else puts("No"); } } return 0; }
我这二逼智商。。。真的够了。。。。
数据结构专题-学习笔记:linkcuttree动态树
1.前言LinkCutTree动态树,简称LCT,是一种维护动态森林的数据结构。前置知识:Splay。2.LCT例题:P3690【模板】动态树(LinkCutTree)2.1实链剖分实链剖分也是一种对树的剖分方式,类似于重链剖分和长链剖分,其将一棵树上的边,随... 查看详情
ac日记——模板linkcuttree洛谷p3690
【模板】LinkCutTree 思路: LCT模板; 代码:#include<bits/stdc++.h>usingnamespacestd;#definemaxn300005intn,m,val[maxn];inttop,ch[maxn][2],f[maxn],xr[maxn],q[maxn],rev[maxn];inlinevoidin(int&now 查看详情
p3690linkcuttree(动态树)
干脆整个LCT模板吧。缺个链上修改和子树操作,链上修改的话join(u,v)然后把vsplay到树根再打个标记就好。至于子树操作...以后有空的话再学(咕咕咕警告)1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4constintN=1e5+10;5intn,m,a[N],X... 查看详情
[]linkcuttree
坑了好久,本来打算就这样弃着,最近又被神秘力量驱使来学这个东西,过程很痛苦但最终还是知道它到底是啥了它可以用来对森林进行各种操作,为了快速地实现各种操作,我们要像树剖一样把整个森林剖成许多条链,每条链... 查看详情
luogu3690模板linkcuttree(动态树)
参考there和there#include<iostream>#include<cstdio>usingnamespacestd;intn,m,val[300005],ch[300005][2],sum[300005],fa[300005],uu,vv,opt;intrev[300005];voidpushDown(intx)if(rev[x])swap(ch[x][0 查看详情
luogup3690模板linkcuttree(动态树)
#include<iostream>#include<cstring>#include<algorithm>#include<cmath>#include<cstdlib>#include<climits>#include<stack>#include<vector>#include<queue& 查看详情
linkcuttree(无图慎入)(代码片段)
类似树链剖分(其实直接记住就可以了),提前放代码1#include<cstdio>2#include<cstdlib>3#include<iostream>4#include<algorithm>5#include<cstring>6#include<climits>7#include<cmath>8#define 查看详情
luogu3690模板linkcuttree(动态树)
题目luogu3690硫硼作者想提醒大家,WA了TLE了RE了的,也许只是主函数写错了代码#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstdlib>#include<cstring>usingnamespacestd 查看详情
linkcuttree求最小生成树(代码片段)
对边建点,原图中的边转化为点的点-边的点-点的点于是用LCT维护连通关系,并支持查询最大值位置即可#include<bits/stdc++.h>usingnamespacestd;constintN=300005;intn,m,val[N],t1,t2,t3;namespacelct inttop,q[N],ch[N][2],fa[N],rev[N]; intmx[N]; inlin 查看详情
ural题目1553.cavesandtunnels(linkcuttree改动点权,求两点之间最大)
1553.CavesandTunnelsTimelimit:3.0secondMemorylimit:64MBAfterlandingonMarssurface,scientistsfoundastrangesystemofcavesconnectedbytunnels.Sotheybegantoresearchitusingremotecontrolledrobots.Itwasfoundout 查看详情
bzoj-2555substring后缀自动机+linkcuttree
2555:SubStringTimeLimit: 30Sec MemoryLimit: 512MBSubmit: 1936 Solved: 551[Submit][Status][Discuss]Description 懒得写背景了,给你一个字符串init,要求你支持两 查看详情
模板linkcuttree(动态树)
题目描述给定N个点以及每个点的权值,要你处理接下来的M个操作。操作有4种。操作从0到3编号。点从1到N编号。0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的... 查看详情
lct(linkcuttree)动态树(代码片段)
模板参考:https://blog.csdn.net/saramanda/article/details/55253627几个知识点:1、LCT中用Splay维护链,这些Splay叫做“辅助树“。辅助树以它上面每个节点的深度为关键字维护,就是辅助树中每个节点左儿子的深度小于当前节点的深度... 查看详情
linkcuttree动态树小结(代码片段)
动态树有些类似树链剖分+并查集的思想,是用splay维护的lct的根是动态的,"轻重链"也是动态的,所以并没有真正的轻重链动态树的操作核心是把你要把修改/询问/...等等一系列的操作的树链放到一个splay里,然后用splay根据相对... 查看详情
luogup3690模板linkcuttree(动态树)lct模板
P3690【模板】LinkCutTree(动态树)题目背景动态树题目描述给定n个点以及每个点的权值,要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和... 查看详情
bzoj-3779重组病毒linkcuttree+线段树+dfs序
3779:重组病毒TimeLimit: 20Sec MemoryLimit: 512MBSubmit: 224 Solved: 95[Submit][Status][Discuss]Description黑客们通过对已有的病毒反编译,将许多不同的病毒重组,并重新编译出了新型的重组病毒。这种病毒的繁殖和... 查看详情
linkcuttree
//知识点:LCT/*By:Luckyblock*/#include<cstdio>#include<ctype.h>#include<algorithm>#definels(t[x].son[0])#definers(t[x].son[1])constintkMaxn=1e5+10;//=============================================================structLink_Cut_Tree_Nodeintson[2],fa;intxr,rev;t[kMaxn];intn,m,val[kMa... 查看详情
洛谷3690:模板linkcuttree——题解(代码片段)
https://www.luogu.org/problemnew/show/P3690给定n个点以及每个点的权值,要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1:... 查看详情