首页 > 代码库 > HDU 4897 Little Devil I
HDU 4897 Little Devil I
_(:3 ⌒?)_ 调我半天，还是记录下吧。
用轻重链可解决此题。
用轻重链的方式给点重新编号后，建两棵线段树，一棵(sumTree)用于记录路径修改，另外一棵(markTree)用于记录邻边修改的点。
然后维护下两棵树即可。
注意，markTree修改时，要在sumTree上修改第一个点和最后一个点对应的重边，若修改的顶点为连接轻链的点，则sumTree对应边不修改。
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<vector>#include<cmath>#include<queue>#include<map>#include<set>#include<stack>#define ll long long#define INF 0x3f3f3f3f#define BUG printf("hehe!~\n")#define lson(x) (x<<1)#define rson(x) (x<<1|1)#define y1 y123123using namespace std;const int N=100010;int n;vector<int> G[N];bool vis[N];int size[N],fa[N],mxson[N];int tot,num[N],top[N],pre[N],dep[N];int y1,y2;struct Node{ int l,r; int rev; int sum;};void DFS(int x){ vis[x]=true; size[x]=1; int v; for(int i=0;i<G[x].size();++i) { v=G[x][i]; if(!vis[v]) { fa[v]=x; DFS(v); size[x]+=size[v]; if(size[v]>size[mxson[x]]) mxson[x]=v; } } vis[x]=false;}void make(int x,int depth,int tp){ ++tot; num[x]=tot; pre[tot]=x; top[x]=tp; dep[x]=depth; vis[x]=true; if(mxson[x]) { make(mxson[x],depth,tp); } int v; for(int i=0;i<G[x].size();++i) { v=G[x][i]; if(!vis[v]&&v!=mxson[x]) { make(v,depth+1,v); } } vis[x]=false;}struct MyTree{ Node T[N<<2]; int _sum;//set 0 void buildtree(int u,int L,int R) { if(L==R) { T[u].l=L; T[u].r=R; T[u].sum=0; return; } int mid=(L+R)>>1; T[u].l=L,T[u].r=R,T[u].sum=0,T[u].rev=0; buildtree(lson(u),L,mid); buildtree(rson(u),mid+1,R); } void maintain(int u,int L,int R) { int lc=lson(u),rc=rson(u); if(R>L) { T[u].sum=T[lc].sum+T[rc].sum; } if(T[u].rev) T[u].sum=T[u].r-T[u].l+1-T[u].sum; } void rever(int u,int L,int R) { //if(y1>y2) return; //if(L>R) return; if(y1<=L&&y2>=R) { T[u].rev^=1; T[u].sum=T[u].r-T[u].l+1-T[u].sum; return; } else { int mid=(L+R)>>1; if(y1<=mid) rever(lson(u),L,mid); if(y2>mid) rever(rson(u),mid+1,R); } maintain(u,L,R); } void querysum(int u,int L,int R,int re) { if(y1<=L&&y2>=R) { if(re) _sum+=T[u].r-T[u].l+1-T[u].sum; else _sum+=T[u].sum; } else { int mid=(L+R)>>1; if(y1<=mid) querysum(lson(u),L,mid,re^T[u].rev); if(y2>mid) querysum(rson(u),mid+1,R,re^T[u].rev); } }}sumTree,markTree;void reverpath(int x,int y){ if(dep[x]>dep[y]) swap(x,y); while(dep[x]<dep[y]) { y1=num[top[y]],y2=num[y]; //cout<<x<<" "<<y<<" "<<y1<<" "<<y2<<endl; if(y1<=y2)sumTree.rever(1,1,n); y=fa[top[y]]; } while(top[x]!=top[y]) { y1=num[top[x]],y2=num[x]; if(y1<=y2) sumTree.rever(1,1,n); y1=num[top[y]],y2=num[y]; if(y1<=y2) sumTree.rever(1,1,n); x=fa[top[x]]; y=fa[top[y]]; } x=num[x],y=num[y]; if(x>y) swap(x,y); y1=x+1,y2=y; //cout<<x<<" "<<y<<" "<<y1<<" "<<y2<<endl; if(top[pre[y1]]==top[pre[y2]]&&y1<=y2) sumTree.rever(1,1,n);}void reveradj(int x,int y){ int ty,tx; if(dep[x]>dep[y]) swap(x,y); while(dep[x]<dep[y]) { y1=num[top[y]],y2=num[y]; if(y1<=y2) markTree.rever(1,1,n); ty=num[y]+1; if(top[pre[ty]]==top[y]) { y1=ty,y2=ty; sumTree.rever(1,1,n); } y=fa[top[y]]; } while(top[x]!=top[y]) { y1=num[top[y]],y2=num[y]; if(y1<=y2) markTree.rever(1,1,n); ty=num[y]+1; if(top[pre[ty]]==top[y]) { y1=ty,y2=ty; sumTree.rever(1,1,n); } y1=num[top[x]],y2=num[x]; if(y1<=y2) markTree.rever(1,1,n); tx=num[x]+1; if(top[pre[tx]]==top[x]) { y1=tx,y2=tx; sumTree.rever(1,1,n); } x=fa[top[x]]; y=fa[top[y]]; } //x=num[x],y=num[y]; if(num[x]>num[y]) swap(x,y); y1=num[x],y2=num[y]; if(y1<=y2) markTree.rever(1,1,n); //tx=num[x]-1; //if(top[pre[tx]]==top[x]) //sumTree.rever(1,tx,tx); if(x!=top[x]) { y1=num[x],y2=num[x]; sumTree.rever(1,1,n); } ty=num[y]+1; if(top[pre[ty]]==top[y]) { y1=ty,y2=ty; sumTree.rever(1,1,n); }}void query(int x,int y){ int ans=0; int lch,rch; if(dep[x]>dep[y]) swap(x,y); while(dep[x]<dep[y]) { y1=num[top[y]]+1,y2=num[y]; sumTree._sum=0; if(y1<=y2) sumTree.querysum(1,1,n,0); ans+=sumTree._sum; sumTree._sum=0; y1=num[top[y]],y2=num[top[y]]; sumTree.querysum(1,1,n,0); lch=sumTree._sum; markTree._sum=0; y1=num[top[y]],y2=num[top[y]]; markTree.querysum(1,1,n,0); rch=markTree._sum; lch^=rch; y=fa[top[y]]; markTree._sum=0; y1=num[y],y2=num[y]; markTree.querysum(1,1,n,0); rch=markTree._sum; lch^=rch; ans+=lch; } while(top[x]!=top[y]) {////////////////////////// y1=num[top[y]]+1,y2=num[y]; sumTree._sum=0; if(y1<=y2) sumTree.querysum(1,1,n,0); ans+=sumTree._sum; sumTree._sum=0; y1=num[top[y]],y2=num[top[y]]; sumTree.querysum(1,1,n,0); lch=sumTree._sum; markTree._sum=0; y1=num[top[y]],y2=num[top[y]]; markTree.querysum(1,1,n,0); rch=markTree._sum; lch^=rch; y=fa[top[y]]; y1=num[y],y2=num[y]; markTree._sum=0; markTree.querysum(1,1,n,0); rch=markTree._sum; lch^=rch; ans+=lch; y1=num[top[x]]+1,y2=num[x]; sumTree._sum=0; if(y1<=y2) sumTree.querysum(1,1,n,0); ans+=sumTree._sum; sumTree._sum=0; y1=num[top[x]],y2=num[top[x]]; sumTree.querysum(1,1,n,0); lch=sumTree._sum; markTree._sum=0; y1=num[top[x]],y2=num[top[x]]; markTree.querysum(1,1,n,0); rch=markTree._sum; lch^=rch; x=fa[top[x]]; markTree._sum=0; y1=num[x],y2=num[x]; markTree.querysum(1,1,n,0); rch=markTree._sum; lch^=rch; ans+=lch; //x=fa[top[x]]; //y=fa[top[y]]; } if(num[x]>num[y]) swap(x,y); sumTree._sum=0; y1=num[x]+1,y2=num[y]; if(y1<=y2) sumTree.querysum(1,1,n,0); ans+=sumTree._sum; printf("%d\n",ans);}int main(){ int _; int Q,c,a,b; cin>>_; while(_--) { scanf("%d",&n); tot=0; for(int i=0;i<=n;++i) G[i].clear(); for(int i=1;i<n;++i) { scanf("%d%d",&a,&b); G[a].push_back(b); G[b].push_back(a); } fa[1]=-1; for(int i=1;i<=n;++i) mxson[i]=0; DFS(1); make(1,1,1); sumTree.buildtree(1,1,n); markTree.buildtree(1,1,n); scanf("%d",&Q); while(Q--) { scanf("%d%d%d",&c,&a,&b); //a=num[a];b=num[b]; if(1==c) reverpath(a,b); else if(2==c) reveradj(a,b); else query(a,b); } }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。