《树链剖分+树的分治》由会员分享，可在线阅读，更多相关《树链剖分+树的分治（53页珍藏版）》请在金锄头文库上搜索。
1、报名方式： 1，将该表交到电教楼522 室，时间下周一，二，三。2，将个人简历发送到。树链剖分 +树的分治spoj 375 树链剖分模板/* 给一颗树，每条边有一个权值。有两种操作：1、修改某条边的值；2、询问 a、b 两点路径上边权的最大值。树链剖分。只是一道树链刨分的入门题,作为模板用。*/ #include #include #include #include #include #include #include using namespace std; #define N 11000 #define inf 0x3fffffff int headN; int sonN;/记录与当前点相
2、连的数目最多的子节点的下标int faN;/记录上一个父节点int sizN;/记录当前节点的子节点的数目int topN;/当前链的最顶层int fN;/重新标记int fpN;/记录重新标记前的点报名方式： 1，将该表交到电教楼522 室，时间下周一，二，三。2，将个人简历发送到。int deepN;/深度int wN;/ 记录当前点与其父节点的关系int nu,yong; int Max; struct nodee int u,v,w,next; bianN*4,ffN; void init() yong=nu=0; memset(head,-1,sizeof(head); memset
3、(son,-1,sizeof(son); void addedge(int u,int v,int w) bianyong.u=u; bianyong.v=v; bianyong.next=headu; headu=yong+; void dfs(int u,int father,int d) deepu=d;/记录深度sizu=1;/初始化fau=father;/记录父节点int i; for(i=headu; i!=-1; i=biani.next) int v=biani.v; 报名方式： 1，将该表交到电教楼522 室，时间下周一，二，三。2，将个人简历发送到。if(v!=father
4、) dfs(v,u,d+1);/ sizu+=sizv;/回溯时累加数目if(sonu=-1|sizsonuvv?v:vv; void pushup(int t) /回溯时更新最大值和最小值 treet.maxx=Ma(treet*2.maxx,treet*2+1.maxx); void build(int t,int l,int r)/建树 treet.l=l; treet.r=r; if(treet.l=treet.r) treet.maxx=wtreet.l;/记录边权值return ; int mid=(l+r)1; build(t*2,l,mid); build(t*2+1,mid+
5、1,r); pushup(t); void qury(int t,int l,int r)/询问区间的最大值 if(treet.l=l/ return ; 报名方式： 1，将该表交到电教楼522 室，时间下周一，二，三。2，将个人简历发送到。int mid=(treet.l+treet.r)1; if(rmid) qury(t*2+1,l,r); else qury(t*2,l,mid); qury(t*2+1,mid+1,r); pushup(t); int findmax(int u,int v)/ 查找最大值 int f1=topu;/得到顶端编号值int f2=topv; int an
6、s=-inf;/初始化最小值while(f1!=f2)/结束条件 ,再通一个重链上 if(deepf1deepv)swap(u,v);/得到 u ，v 之间的最小值Max=-inf; qury(1,fsonu,fv);/求出 u 的子节点的fv-fu的最大数目子节点;,因为此时他们在一个重链上ans=Ma(ans,Max);/求出最大值return ans; void update(int t,int x,int y)/更新 if(treet.l=x return ; int mid=(treet.l+treet.r)/2; if(x #include #include #include #i
7、nclude #include #include using namespace std; #define N 11000 #define inf 0x3fffffff int headN; int sonN;/记录与当前点相连的数目最多的子节点的下标int faN;/记录上一个父节点int sizN;/记录当前节点的子节点的数目int topN;/当前链的最顶层int fN;/重新标记int fpN;/记录重新标记前的点int deepN;/深度int wN;/ 记录当前点与其父节点的关系int nu,yong; int Max; struct nodee 报名方式： 1，将该表交到电教楼5
8、22 室，时间下周一，二，三。2，将个人简历发送到。int u,v,w,next; bianN*4,ffN; void init() yong=nu=0; memset(head,-1,sizeof(head); memset(son,-1,sizeof(son); void addedge(int u,int v,int w) bianyong.u=u; bianyong.v=v; bianyong.next=headu; headu=yong+; void dfs(int u,int father,int d) deepu=d;/记录深度sizu=1;/初始化fau=father;/记录父
9、节点int i; for(i=headu; i!=-1; i=biani.next) int v=biani.v; if(v!=father) dfs(v,u,d+1);/ sizu+=sizv;/回溯时累加数目if(sonu=-1|sizsonuvv?v:vv; int Min(int v,int vv) 报名方式： 1，将该表交到电教楼522 室，时间下周一，二，三。2，将个人简历发送到。return vvv?vv:v; void pushdown(int t) while(treet.yanchi) treet*2.maxx=-treet*2.maxx; treet*2.minn=-tr
10、eet*2.minn; swap(treet*2.maxx,treet*2.minn); treet*2.yanchi=1; treet*2+1.maxx=-treet*2+1.maxx; treet*2+1.minn=-treet*2+1.minn; swap(treet*2+1.maxx,treet*2+1.minn); treet*2+1.yanchi=1; treet.yanchi=0; return ; void pushup(int t) /回溯时更新最大值和最小值 treet.maxx=Ma(treet*2.maxx,treet*2+1.maxx); treet.minn=Min
11、(treet*2.minn,treet*2+1.minn); void build(int t,int l,int r)/建树 treet.l=l; treet.r=r; treet.yanchi=0; if(treet.l=treet.r) treet.maxx=treet.minn=wtreet.l;/记录边权值return ; 报名方式： 1，将该表交到电教楼522 室，时间下周一，二，三。2，将个人简历发送到。 int mid=(l+r)1; build(t*2,l,mid); build(t*2+1,mid+1,r); pushup(t); void qury(int t,int l
12、,int r)/询问区间的最大值 if(treet.l=l/ return ; int mid=(treet.l+treet.r)1; pushdown(t); if(rmid) qury(t*2+1,l,r); else qury(t*2,l,mid); qury(t*2+1,mid+1,r); pushup(t); int findmax(int u,int v)/ 查找最大值 int f1=topu;/得到顶端编号值int f2=topv; 报名方式： 1，将该表交到电教楼522 室，时间下周一，二，三。2，将个人简历发送到。int ans=-inf;/初始化最小值while(f1!=f
13、2)/结束条件 ,再通一个重链上 if(deepf1deepv)swap(u,v);/得到 u ，v 之间的最小值Max=-inf; qury(1,fsonu,fv);/求出 u 的子节点的fv-fu的最大数目子节点;,因为此时他们在一个重链上ans=Ma(ans,Max);/求出最大值return ans; void update(int t,int x,int y)/更新 if(treet.l=x return ; 报名方式： 1，将该表交到电教楼522 室，时间下周一，二，三。2，将个人简历发送到。pushdown(t); int mid=(treet.l+treet.r)/2; if(
14、xmid)chant(t*2+1,l,r); else chant(t*2,l,mid); chant(t*2+1,mid+1,r); pushup(t); void change(int u,int v) int f1=topu; int f2=topv; while(f1!=f2) 报名方式： 1，将该表交到电教楼522 室，时间下周一，二，三。2，将个人简历发送到。if(deepf1deepv)swap(u,v); chant(1,fsonu,fv); return ; int main() int T,i,n; scanf(“%d“, while(T-) scanf(“%d“, init(); for(i=1; i #include #include #include #include using namespace std; #define N 110000 #define inf 0x3fffffff int fN; int topN; int faN; int sizN; int nu,yong; int headN;
