首页 > 代码库 > 【POJ3237】Tree 树链剖分
【POJ3237】Tree 树链剖分
题意:
change,把第i条边权值改成v
negate,把a到b路径上所有权值取相反数(*(-1))
query,询问a到b路径上所有权值的最大值
树链剖分。
以前一直不会,但是我恶补LCT了,所以先学一下。
对于现在的水平来说,树剖太水了,自己翻资料吧,我只提供一个还算不错的代码。
扒代码的时候可以用我的这个。
附rand和pai。
代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 10100 #define inf 0x3f3f3f3f using namespace std; struct KSD { int u,v,len,next; }e[N<<1],road[N]; int head[N],cnt; void add(int u,int v,int len) { ++cnt; e[cnt].v=v; e[cnt].len=len; e[cnt].next=head[u]; head[u]=cnt; } struct Segment_Tree { int l,r; int in,ax; bool lazy; }s[N<<2]; int n,m,root=1; int deep[N],Fa[N],son[N],size[N];// 深度,父节点,重儿子 int top[N],pos[N],len[N],ll[N]; char opt[10]; void init() { cnt=0; memset(top,0,sizeof(top)); memset(son,0,sizeof(son)); memset(head,0,sizeof(head)); } void dfs1(int x,int p)// 确定轻重儿子 { int i,v,temp=0; deep[x]=deep[p]+1; size[x]=1; Fa[x]=p; for(i=head[x];i;i=e[i].next) { v=e[i].v; if(v==p)continue; dfs1(v,x); size[x]+=size[v]; ll[v]=e[i].len; if(temp<size[v])temp=size[v],son[x]=v; } return ; } void dfs2(int x,int p,int r)// 确定轻重链,并将它们串起来 { int i,v; pos[x]=++cnt; len[cnt]=ll[x]; top[x]=r; if(son[x])dfs2(son[x],x,top[x]);// 先走重链保证dfs序的性质。 for(i=head[x];i;i=e[i].next) { v=e[i].v; if(v==p||v==son[x])continue; dfs2(v,x,v); } } void pushup(int x) { s[x].in=min(s[x<<1].in,s[x<<1|1].in); s[x].ax=max(s[x<<1].ax,s[x<<1|1].ax); } void pushdown(int x) { if(s[x].lazy)// 取反 { if(s[x].l<s[x].r)s[x<<1].lazy^=1,s[x<<1|1].lazy^=1; int t=s[x].in;s[x].in=-s[x].ax;s[x].ax=-t; s[x].lazy=0; } } void build(int note,int l,int r) { s[note].lazy=0; s[note].l=l,s[note].r=r; if(l==r) { s[note].ax=s[note].in=len[l]; if(l==1)s[note].in=inf,s[note].ax=-inf; return ; } int mid=l+r>>1; build(note<<1,l,mid); build(note<<1|1,mid+1,r); pushup(note); } void change(int note,int L,int R,int x,int y) { pushdown(note); if(L==R) { s[note].in=s[note].ax=y; return ; } int mid=L+R>>1; if(x<=mid)change(note<<1,L,mid,x,y),pushdown(note<<1|1); else change(note<<1|1,mid+1,R,x,y),pushdown(note<<1); pushup(note); } int ASK(int note,int L,int R,int l,int r) { if(l>r)return -inf; pushdown(note); if(L==l&&r==R)return s[note].ax; int mid=L+R>>1; if(r<=mid)return ASK(note<<1,L,mid,l,r); else if(l>mid)return ASK(note<<1|1,mid+1,R,l,r); else return max(ASK(note<<1,L,mid,l,mid),ASK(note<<1|1,mid+1,R,mid+1,r)); } int ask(int a,int b) { int fa,fb,ans=-inf; for(fa=top[a],fb=top[b];fa!=fb;a=Fa[top[a]],fa=top[a]) { if(deep[fa]<deep[fb])swap(a,b),swap(fa,fb); ans=max(ans,ASK(1,1,n,pos[fa],pos[a])); } if(a!=b) { if(deep[a]<deep[b])swap(a,b); ans=max(ans,ASK(1,1,n,pos[b]+1,pos[a])); } return ans; } void NEGATE(int note,int L,int R,int l,int r) { if(L==l&&r==R) { s[note].lazy^=1; pushdown(note); return ; } pushdown(note); int mid=L+R>>1; if(r<=mid)NEGATE(note<<1,L,mid,l,r),pushdown(note<<1|1); else if(l>mid)NEGATE(note<<1|1,mid+1,R,l,r),pushdown(note<<1); else NEGATE(note<<1,L,mid,l,mid),NEGATE(note<<1|1,mid+1,R,mid+1,r); pushup(note); } void _negate(int a,int b) { int fa,fb; for(fa=top[a],fb=top[b];fa!=fb;a=Fa[top[a]],fa=top[a]) { if(deep[fa]<deep[fb])swap(a,b),swap(fa,fb); NEGATE(1,1,n,pos[fa],pos[a]); } if(a!=b) { if(deep[a]<deep[b])swap(a,b); NEGATE(1,1,n,pos[b]+1,pos[a]); } } int main() { // freopen("test.in","r",stdin); // freopen("my.out","w",stdout); int i,j,k,g; int a,b,c; scanf("%d",&g); while(g--) { init(); scanf("%d",&n); for(i=1;i<n;i++) { scanf("%d%d%d",&road[i].u,&road[i].v,&road[i].len); add(road[i].u,road[i].v,road[i].len); add(road[i].v,road[i].u,road[i].len); } cnt=0; dfs1(root,0); dfs2(root,0,root); build(1,1,n); while(scanf("%s",opt),opt[0]!='D') { scanf("%d%d",&a,&b); if(opt[0]=='Q')printf("%d\n",ask(a,b)); else if(opt[0]=='N')_negate(a,b); else change(1,1,n,pos[Fa[road[a].u]==road[a].v?road[a].u:road[a].v],b); } } return 0; }rand:
#include <ctime> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int main() { int i,j,k; freopen("test.in","w",stdout); puts("1"); srand((unsigned)time(NULL)); int n=5; printf("%d\n",n); for(i=1;i<n;i++) { printf("%d %d %d\n",i+1,rand()%i+1,rand()%14513546); } for(i=1;i<n;i++) { int opt=rand()%3; if(opt==0) { printf("CHANGE %d %d\n",rand()%(n-1)+1,rand()%42534567); } else if(opt==1) { int a=0,b=0; while(a==b)a=rand()%n+1,b=rand()%n+1; printf("NEGATE %d %d\n",a,b); } else { int a=0,b=0; while(a==b)a=rand()%n+1,b=rand()%n+1; printf("QUERY %d %d\n",a,b); } } puts("DONE"); fclose(stdout); return 0; }pai
#include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> using namespace std; int main() { int i,j,k; for(i=1;i<=3000;i++) { system("rand"); system("my"); system("std"); printf("Case %04d : ",i); if(system("fc my.out std.out > NULL")==0) { puts("AC"); } else { puts("WAWAWWAWAWWWA"); system("pause"); return 0; } } system("pause"); return 0; }
【POJ3237】Tree 树链剖分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。