首页 > 代码库 > bzoj4353: Play with tree
bzoj4353: Play with tree
Description
给你一棵包含N个节点的树，设每条边一开始的边权为0，现在有两种操作：
1）给出参数U,V,C，表示把U与V之间的路径上的边权变成C（保证C≥0）
2）给出参数U,V,C，表示把U与V之间的路径上的边权加上C。但是如果U至V之间路径某条边的边权加上C小于0，那么C=这条边的边权的相反数。
你需要统计出每次一操作过后树中边权为0的边有多少条。
Input
第一行两个整数N,M，分别表示表示节点个数与操作数。
接下来N-1行每行两个整数X,Y表示X,Y之间有一条边。
接下来M行每行4个整数P,U,V,C，P表示操作类型，U,V,C的意义见题目描述。
Output
输出文件包括M行，每行一个整数，表示边权为0的边的个数。
树链剖分+线段树维护一下区间最小值和个数、覆盖标记、加法标记
#include<cstdio>#include<algorithm>typedef long long i64;const int N=100007;const i64 fil_0=1ll<<60;char buf[6000007],*ptr=buf-1;int _(){ int x=0,c=*++ptr,f=1; while(c<48)c==‘-‘&&(f=-1),c=*++ptr; while(c>47)x=x*10+c-48,c=*++ptr; return x*f;}int n,m,es[N*2],enx[N*2],e0[N],ep=2,ans=0;int fa[N],sz[N],dep[N],top[N],son[N],id[N],idp=0;int _l,_r;i64 _a;struct node{ node*lc,*rc; i64 mn,fil,a; int L,R,mc; int c0(){ return mn?0:mc; } void _fil(i64 x){ mn=fil=x; mc=R-L+1; a=0; } void _add(i64 x){ if(fil!=fil_0)fil+=x; mn+=x;a+=x; } void fils(){ if(_l<=L&&R<=_r){ _fil(_a); return; } dn(); int M=L+R>>1; if(_l<=M)lc->fils(); if(_r>M)rc->fils(); up(); } void mns(){ if(mn>=_a)return; if(_l<=L&&R<=_r){ _a=mn; return; } dn(); int M=L+R>>1; if(_l<=M)lc->mns(); if(_r>M)rc->mns(); } void adds(){ if(_l<=L&&R<=_r){ _add(_a); return; } dn(); int M=L+R>>1; if(_l<=M)lc->adds(); if(_r>M)rc->adds(); up(); } void dn(){ if(a){ lc->_add(a); rc->_add(a); a=0; } if(fil!=fil_0){ lc->_fil(fil); rc->_fil(fil); fil=fil_0; } } void up(){ mn=lc->mn<rc->mn?lc->mn:rc->mn; mc=0; if(mn==lc->mn)mc+=lc->mc; if(mn==rc->mn)mc+=rc->mc; }}ns[N*2],*np=ns,*rt[N];node*build(int L,int R){ node*w=np++; w->L=L;w->R=R; if(L!=R){ int M=L+R>>1; w->lc=build(L,M); w->rc=build(M+1,R); w->up(); }else{ w->mn=0;w->mc=1; w->fil=fil_0; } return w;}#define F(a,b) ans-=a->c0(),a->b(),ans+=a->c0()void fils(int x,int y,i64 c){ int a=top[x],b=top[y]; _a=c; while(a!=b){ if(dep[a]<dep[b])std::swap(a,b),std::swap(x,y); _l=id[a],_r=id[x]; F(rt[a],fils); x=fa[a];a=top[x]; } if(dep[x]>dep[y])std::swap(x,y); _l=id[x]+1,_r=id[y]; if(_l<=_r)F(rt[top[x]],fils);}void mns(int x,int y,i64 c){ int a=top[x],b=top[y]; _a=c; while(a!=b){ if(dep[a]<dep[b])std::swap(a,b),std::swap(x,y); _l=id[a],_r=id[x]; rt[a]->mns(); x=fa[a];a=top[x]; } if(dep[x]>dep[y])std::swap(x,y); _l=id[x]+1,_r=id[y]; if(_l<=_r)rt[top[x]]->mns();}void adds(int x,int y,i64 c){ mns(x,y,-c); _a*=-1; int a=top[x],b=top[y]; while(a!=b){ if(dep[a]<dep[b])std::swap(a,b),std::swap(x,y); _l=id[a],_r=id[x]; F(rt[a],adds); x=fa[a];a=top[x]; } if(dep[x]>dep[y])std::swap(x,y); _l=id[x]+1,_r=id[y]; if(_l<=_r)F(rt[top[x]],adds);}void f1(int w,int pa){ dep[w]=dep[fa[w]=pa]+1; sz[w]=1; for(int i=e0[w];i;i=enx[i]){ int u=es[i]; if(u!=pa){ f1(u,w); sz[w]+=sz[u]; if(sz[u]>sz[son[w]])son[w]=u; } }}void f2(int w,int tp){ top[w]=tp; id[w]=++idp; if(son[w])f2(son[w],tp); else rt[tp]=build(id[tp],id[w]); for(int i=e0[w];i;i=enx[i]){ int u=es[i]; if(u!=fa[w]&&u!=son[w])f2(u,u); }}int main(){ buf[fread(buf,1,sizeof(buf),stdin)]=0; n=_();m=_(); for(int i=1,a,b;i<n;++i){ a=_();b=_(); es[ep]=b;enx[ep]=e0[a];e0[a]=ep++; es[ep]=a;enx[ep]=e0[b];e0[b]=ep++; } f1(1,0);f2(1,1); ans=n-1; for(int i=0,o,u,v,c;i<m;++i){ o=_();u=_();v=_();c=_(); if(o==1)fils(u,v,c); else adds(u,v,c); printf("%d\n",ans); } return 0;}
bzoj4353: Play with tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。