[Codeforces343D]Water Tree（树链剖分）

题目描述

传送门

题解

题如其名

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define N 500005 int n,m,dfs_clock; int tot,point[N],nxt[N*2],v[N*2]; int size[N],father[N],h[N],son[N],in[N],out[N],top[N]; int tr[N*4],delta[N*4]; void add(int x,int y) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; } void dfs_1(int x,int fa) { size[x]=1;father[x]=fa;h[x]=h[fa]+1; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa) { dfs_1(v[i],x); size[x]+=size[v[i]]; if (size[v[i]]>size[son[x]]) son[x]=v[i]; } } void dfs_2(int x,int fa) { if (x==son[fa]) top[x]=top[fa]; else top[x]=x; in[x]=++dfs_clock; if (son[x]) dfs_2(son[x],x); for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&v[i]!=son[x]) dfs_2(v[i],x); out[x]=dfs_clock; } void pushdown(int now,int l,int r,int mid) { if (delta[now]!=-1) { tr[now<<1]=delta[now<<1]=delta[now]; tr[now<<1|1]=delta[now<<1|1]=delta[now]; delta[now]=-1; } } void change(int now,int l,int r,int lr,int rr,int opt) { int mid=(l+r)>>1; if (lr<=l&&r<=rr) { tr[now]=opt; delta[now]=opt; return; } pushdown(now,l,r,mid); if (lr<=mid) change(now<<1,l,mid,lr,rr,opt); if (mid+1<=rr) change(now<<1|1,mid+1,r,lr,rr,opt); } int query(int now,int l,int r,int x) { int mid=(l+r)>>1; if (l==r) return tr[now]; pushdown(now,l,r,mid); if (x<=mid) return query(now<<1,l,mid,x); else return query(now<<1|1,mid+1,r,x); } void CHANGE(int u,int t) { int f1=top[u],f2=top[t]; while (f1!=f2) { if (h[f1]<h[f2]) { swap(f1,f2); swap(u,t); } change(1,1,n,in[f1],in[u],0); u=father[f1]; f1=top[u]; } if (in[u]>in[t]) swap(u,t); change(1,1,n,in[u],in[t],0); } int main() { scanf("%d",&n); for (int i=1;i<n;++i) { int x,y;scanf("%d%d",&x,&y); add(x,y),add(y,x); } dfs_1(1,0); dfs_2(1,0); memset(delta,-1,sizeof(delta)); scanf("%d",&m); for (int i=1;i<=m;++i) { int opt,x;scanf("%d%d",&opt,&x); if (opt==1) change(1,1,n,in[x],out[x],1); if (opt==2) CHANGE(1,x); if (opt==3) { int ans=query(1,1,n,in[x]); printf("%d\n",ans); } } }

手工栈

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define N 500005 int n,m,dfs_clock; int tot,point[N],nxt[N*2],v[N*2]; int size[N],father[N],h[N],son[N],in[N],out[N],top[N]; int cur[N],stack[N];bool use[N]; int tr[N*4],delta[N*4]; void add(int x,int y) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; } void dfs_1() { for (int i=1;i<=n;++i) cur[i]=point[i]; size[1]=1,father[1]=0,h[1]=1; int tmp=0;stack[++tmp]=1; while (tmp) { int x=stack[tmp]; while (cur[x]&&v[cur[x]]==father[x]) cur[x]=nxt[cur[x]]; if (!cur[x]) { --tmp; if (father[x]) { size[father[x]]+=size[x]; if (size[x]>size[son[father[x]]]) son[father[x]]=x; } continue; } int vt=v[cur[x]]; size[vt]=1,father[vt]=x,h[vt]=h[x]+1; stack[++tmp]=vt; cur[x]=nxt[cur[x]]; } } void dfs_2() { for (int i=1;i<=n;++i) cur[i]=point[i]; in[1]=++dfs_clock,top[1]=1; int tmp=0;stack[++tmp]=1; while (tmp) { int x=stack[tmp]; if (!use[x]) { use[x]=1; if (son[x]) { int vt=son[x]; in[vt]=++dfs_clock,top[vt]=top[x]; stack[++tmp]=vt; continue; } } while (cur[x]&&(v[cur[x]]==father[x]||v[cur[x]]==son[x])) cur[x]=nxt[cur[x]]; if (!cur[x]) { out[x]=dfs_clock; --tmp; continue; } int vt=v[cur[x]]; in[vt]=++dfs_clock,top[vt]=vt; stack[++tmp]=vt; cur[x]=nxt[cur[x]]; } } void pushdown(int now,int l,int r,int mid) { if (delta[now]!=-1) { tr[now<<1]=delta[now<<1]=delta[now]; tr[now<<1|1]=delta[now<<1|1]=delta[now]; delta[now]=-1; } } void change(int now,int l,int r,int lr,int rr,int opt) { int mid=(l+r)>>1; if (lr<=l&&r<=rr) { tr[now]=opt; delta[now]=opt; return; } pushdown(now,l,r,mid); if (lr<=mid) change(now<<1,l,mid,lr,rr,opt); if (mid+1<=rr) change(now<<1|1,mid+1,r,lr,rr,opt); } int query(int now,int l,int r,int x) { int mid=(l+r)>>1; if (l==r) return tr[now]; pushdown(now,l,r,mid); if (x<=mid) return query(now<<1,l,mid,x); else return query(now<<1|1,mid+1,r,x); } void CHANGE(int u,int t) { int f1=top[u],f2=top[t]; while (f1!=f2) { if (h[f1]<h[f2]) { swap(f1,f2); swap(u,t); } change(1,1,n,in[f1],in[u],0); u=father[f1]; f1=top[u]; } if (in[u]>in[t]) swap(u,t); change(1,1,n,in[u],in[t],0); } int main() { scanf("%d",&n); for (int i=1;i<n;++i) { int x,y;scanf("%d%d",&x,&y); add(x,y),add(y,x); } dfs_1(); dfs_2(); memset(delta,-1,sizeof(delta)); scanf("%d",&m); for (int i=1;i<=m;++i) { int opt,x;scanf("%d%d",&opt,&x); if (opt==1) change(1,1,n,in[x],out[x],1); if (opt==2) CHANGE(1,x); if (opt==3) { int ans=query(1,1,n,in[x]); printf("%d\n",ans); } } }