【2019.7.25 NOIP模拟赛 T3】树（tree）（dfs序列上开线段树）

没有换根操作

考虑如果没有换根操作，我们该怎么做。

我们可以求出原树的\(dfs\)序列，然后开线段树维护。

对于修改操作，我们可以倍增求\(LCA\)，然后在线段树上修改子树内的值。

对于询问操作，我们直接查询子树内的值。

但有了换根操作，\(LCA\)就可能不再是原来的\(LCA\)，子树也就可能不再是原来的子树了。

换根操作后的\(LCA\)

通过一波画图+找规律，我们可以发现，在根为\(rt\)时，换根操作后的\(LCA(x,y)\)大致有如下几种情况：（以下讨论中\(x,y\)互换同理）

若\(rt\)在\(x\)的子树内，且\(y\)也在\(x\)的子树内，\(LCA\)就是\(LCA(y,rt)\)。
若\(rt\)在\(x\)的子树内，但\(y\)不在\(x\)的子树内，\(LCA\)就是\(x\)。
若\(x\)在\(rt\)的子树内，且\(y\)不在\(rt\)的子树内，\(LCA\)就是\(rt\)。
除去以上情况，设\(t=LCA(x,y)\)，若\(rt\)不在\(t\)的子树内，\(LCA\)就是\(t\)。
否则，设\(t1=LCA(x,rt),t2=LCA(y,rt)\)，\(LCA\)就是\(t1\)与\(t2\)中深度较大的那个。

是不是很复杂？

换根操作后的子树

这比\(LCA\)良心多了，只用分两种情况讨论。

若\(rt\)不在\(x\)子树内，处理的就是\(x\)的子树。

否则，我们找到\(rt\)在\(x\)哪个儿子的子树内，然后处理树上除该子树外的其他部分。其实就是\(dfs\)序列中的一段前缀和一段后缀。

不过除了这两种情况外，还有一种特殊情况需要注意，即\(x=rt\)时，处理整棵树。

代码

#pragma GCC optimize(2)

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 300000

#define LN 20

#define LL long long

#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)

#define swap(x,y) (x^=y^=x^=y)

using namespace std;

int n,Qt,rt=1,ee,lnk[N+5];LL a[N+5];struct edge {int to,nxt;}e[N<<1];

class FastIO

{

	private:

		#define FS 100000

		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)

		#define pc(c) (C==E&&(clear(),0),*C++=c)

		#define tn (x<<3)+(x<<1)

		#define D isdigit(c=tc())

		int f,T;char c,*A,*B,*C,*E,FI[FS],FO[FS],S[FS];

	public:

		I FastIO() {A=B=FI,C=FO,E=FO+FS;}

		Tp I void read(Ty& x) {x=0,f=1;W(!D) f=c^'-'?1:-1;W(x=tn+(c&15),D);x*=f;}

		Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}

		Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}

		Tp I void writeln(Con Ty& x) {write(x),pc('\n');}

		I void clear() {fwrite(FO,1,C-FO,stdout),C=FO;}

}F;

template<int SZ> class SegmentTree//线段树

{

	private:

		#define L l,mid,rt<<1

		#define R mid+1,r,rt<<1|1

		#define PU(x) (V[x]=V[x<<1]+V[x<<1|1])

		#define PD(x,ls,rs) F[x]&&(U(x<<1,F[x],ls),U(x<<1|1,F[x],rs),F[x]=0)

		#define U(x,v,s) (V[x]+=1LL*(s)*v,F[x]+=v)

		int n;LL V[N<<2],F[N<<2];

		I void Build(LL *a,int *fac,CI l,CI r,CI rt)//建树

		{

			if(l==r) return (void)(V[rt]=a[fac[l]]);RI mid=l+r>>1;

			Build(a,fac,L),Build(a,fac,R),PU(rt);

		}

		I void Upt(CI tl,CI tr,CI tv,CI l,CI r,CI rt)//区间修改

		{

			if(tl<=l&&r<=tr) return (void)U(rt,tv,r-l+1);RI mid=l+r>>1;PD(rt,mid-l+1,r-mid);

			tl<=mid&&(Upt(tl,tr,tv,L),0),tr>mid&&(Upt(tl,tr,tv,R),0),PU(rt);

		}

		I LL Qry(CI tl,CI tr,CI l,CI r,CI rt)//区间询问

		{

			if(tl<=l&&r<=tr) return V[rt];RI mid=l+r>>1;PD(rt,mid-l+1,r-mid);

			return (tl<=mid?Qry(tl,tr,L):0)+(tr>mid?Qry(tl,tr,R):0);

		}

	public:

		I void Init(CI _n,LL *a,int *fac) {Build(a,fac,1,n=_n,1);}

		I void Upt(CI l,CI r,CI v) {l<=r&&(Upt(l,r,v,1,n,1),0);}

		I LL Qry(CI l,CI r) {return l<=r?Qry(l,r,1,n,1):0;}

};

class DfnSolver//dfs序列上开线段树

{

	private:

		#define Include(x,y) (dfn[x]<=dfn[y]&&dfn[y]<=dfn[x]+Sz[x]-1)

		int d,dep[N+5],fa[N+5][LN+5],Sz[N+5],dfn[N+5],fac[N+5];SegmentTree<N> S;

		I void dfs(CI x=1)//dfs求出dfs序

		{

			RI i;for(fac[dfn[x]=++d]=x,i=1;i<=LN;++i) fa[x][i]=fa[fa[x][i-1]][i-1];//预处理倍增祖先

			for(Sz[x]=1,i=lnk[x];i;i=e[i].nxt) e[i].to^fa[x][0]&&

				(dep[e[i].to]=dep[fa[e[i].to][0]=x]+1,dfs(e[i].to),Sz[x]+=Sz[e[i].to]);

		}

		I int LCA(RI x,RI y)//倍增求LCA

		{

			RI i;for(dep[x]<dep[y]&&swap(x,y),i=0;dep[x]^dep[y];++i) (dep[x]^dep[y])>>i&1&&(x=fa[x][i]);

			if(x==y) return x;for(i=LN;~i;--i) fa[x][i]^fa[y][i]&&(x=fa[x][i],y=fa[y][i]);return fa[x][0];

		}

		I int GetLCA(CI x,CI y)//求出换根操作后的LCA，分类讨论

		{

			if(Include(x,rt)) return Include(x,y)?LCA(y,rt):x;

			if(Include(y,rt)) return Include(y,x)?LCA(x,rt):y;

			if(Include(rt,x)^Include(rt,y)) return rt;

			RI t=LCA(x,y);if(!Include(t,rt)) return t;

			RI t1=LCA(x,rt),t2=LCA(y,rt);return dep[t1]>dep[t2]?t1:t2;

		}

		I int Jump(RI x,RI d) {for(RI i=0;dep[x]^d;++i) (dep[x]^d)>>i&1&&(x=fa[x][i]);return x;}//树上倍增，跳到对应深度

		I void Upt(CI x,CI v)//修改子树

		{

			if(x==rt) return S.Upt(1,n,v);if(!Include(x,rt)) return S.Upt(dfn[x],dfn[x]+Sz[x]-1,v);

			RI k=Jump(rt,dep[x]+1);S.Upt(1,dfn[k]-1,v),S.Upt(dfn[k]+Sz[k],n,v);

		}

		I LL Qry(CI x)//询问子树

		{

			if(x==rt) return S.Qry(1,n);if(!Include(x,rt)) return S.Qry(dfn[x],dfn[x]+Sz[x]-1);

			RI k=Jump(rt,dep[x]+1);return S.Qry(1,dfn[k]-1)+S.Qry(dfn[k]+Sz[k],n);

		}

	public:

		I void Solve()

		{

			dfs(),S.Init(n,a,fac);RI op,x,y,v;

			W(Qt--) switch(F.read(op,x),op)//读入操作并处理

			{

				case 1:rt=x;break;

				case 2:F.read(y,v),Upt(GetLCA(x,y),v);break;

				case 3:F.writeln(Qry(x));break;

			}

		}

}T;

int main()

{

	freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);

	RI i,x,y;for(F.read(n,Qt),i=1;i<=n;++i) F.read(a[i]);

	for(i=1;i^n;++i) F.read(x,y),add(x,y),add(y,x);return T.Solve(),F.clear(),0;

}

巴特西

【2019.7.25 NOIP模拟赛 T3】树（tree）（dfs序列上开线段树）

没有换根操作

换根操作后的\(LCA\)

换根操作后的子树

代码

最新文章

热门文章