LGP3703题解

不会数据结构石锤了/kk

题意清晰。

我们看到 \(1\) 操作比较奇怪，考虑从 \(1\) 操作入手。

设 \(f_u\) 为 \(u\) 到根节点一共有多少种颜色，我们使用树剖来维护这个东西。

考虑进行 \(1\) 操作时，分三种情况进行讨论：

\(v\) 是 \(u\) 的祖先

直接令 \(f_v = 1\) 就行了。

\(v\) 在 \(u\) 子树内

减掉 \(f_u+1\) 即可。

\(u,v\) 没有祖先关系。

来到了最困难的一部分。

我们可以发现一件很神奇的事情：

某次修改 \(u\) 后，该节点到某个节点的颜色都是相同的，越往后面修改，这个节点的深度就越大，且为 \(u\) 的祖先。

换句话说每种颜色在树上最多只有一段。

考虑暴力执行每个操作，也就是将到根节点的颜色段分别替换成自身的颜色。

如何证明复杂度？

对于这种题，操作明显是可以迁移到序列上的。树剖，不过就是有 \(\log n\) 个序列而已。

所以如果我们能够证明对序列的操作是 \(O(\mathcal M(n))\) 的，自然就证明了全局下这个操作是 \(O(\mathcal M(n)\log n)\) 的。

对于序列，因为每种颜色在树上最多只有一段，我们也可以认为每种颜色在每个序列上最多只有一段。

那么就很好解释了。删掉这一段时，前面的修改全部木大，此时这个前缀的颜色段数量一定不会减少，整个序列的颜色段最多增加 \(1\) 段。

若一个前缀都是同一个颜色时，那么这个颜色被加入一次，删掉一个颜色，复杂度 \(O(1)\)。

反之一定会令某一种颜色断子绝孙，每个颜色最多被断子绝孙一次，所以均摊下来复杂度是 \(O(3)=O(1)\) 的。

于是，我们证明了操作次数是 \(O(\log n)\) 次。

所以 \(1\) 操作的复杂度加上线段树是 \(O(\log^2n)\) 的。

那么 \(2\) 操作和 \(3\) 操作就非常简单了，分别是 \(f_u+f_v-2 \times f_{lca(u,v)}+1\) 和区间最值。

至于这道题的 LCT 做法，由于一个颜色只存在于一条链上，所以直接使用一颗 Splay 来存下这个颜色。

使用 LCT 修改时也是和树剖一样的暴力跳，只不过答案需要在线段树数组上更新。但是因为都知道 LCT 的复杂度是均摊 \(O(\log n)\) 的，所以使用 LCT 的复杂度一定是对的。

也就是说，我们刚才其实证明了 LCT 的复杂度是均摊 \(O(\log n)\) 的（

#include<cstdio>

typedef unsigned ui;

const ui M=1e5+5;

ui n,m,cnt,dfc,h[M],L[M],R[M],f[M],chi[M][2];ui d[M],fa[M],dfn[M],siz[M],Son[M],top[M];

ui mx[M<<2],tag[M<<2];

struct Edge{

	ui v,nx;

}e[M<<1];

inline void Add(const ui&u,const ui&v){

	e[++cnt]=(Edge){v,h[u]};h[u]=cnt;

	e[++cnt]=(Edge){u,h[v]};h[v]=cnt;

}

inline ui max(const ui&a,const ui&b){

	return a>b?a:b;

}

inline void pushdown(const ui&u){

	if(tag[u])mx[u<<1]+=tag[u],tag[u<<1]+=tag[u],mx[u<<1|1]+=tag[u],tag[u<<1|1]+=tag[u],tag[u]=0;

}

inline void update(const ui&u){

	mx[u]=max(mx[u<<1],mx[u<<1|1]);

}

void Modify(const ui&u,const ui&l,const ui&r,const ui&V,const ui&L=1,const ui&R=n){

	if(l>R||L>r)return;if(l<=L&&R<=r)return tag[u]+=V,mx[u]+=V,void();

	const ui&mid=L+R>>1;pushdown(u);Modify(u<<1,l,r,V,L,mid);Modify(u<<1|1,l,r,V,mid+1,R);update(u);

}

ui Query(const ui&u,const ui&l,const ui&r,const ui&L=1,const ui&R=n){

	if(l>R||L>r)return 0;if(l<=L&&R<=r)return mx[u];

	const ui&mid=L+R>>1;pushdown(u);return max(Query(u<<1,l,r,L,mid),Query(u<<1|1,l,r,mid+1,R));

}

inline bool son(const ui&u){

	return chi[f[u]][1]==u;

}

inline bool check(const ui&u){

	return chi[f[u]][son(u)]==u;

}

inline void connect(const ui&u,const ui&fa,const bool&son,const ui&typ){

	if(fa&&typ)chi[fa][son]=u;if(u)f[u]=fa;

}

inline void rotate(ui u){

	ui v=f[u];const bool&typ=son(u);

	connect(chi[u][!typ],v,typ,true);

	connect(u,f[v],son(v),check(v));

	connect(v,u,!typ,true);

}

inline void Splay(const ui&u){

	for(ui v;check(u);rotate(u))if(check(v=f[u]))rotate(son(u)^son(v)?u:v);

}

inline ui findroot(ui u){

	while(chi[u][0])u=chi[u][0];return u;

}

inline void Access(ui u){

	for(ui x,v=0;u;u=f[v=u]){

		Splay(u);

		if(chi[u][1])x=findroot(chi[u][1]),Modify(1,L[x],R[x],1);

		if(chi[u][1]=v)x=findroot(chi[u][1]),Modify(1,L[x],R[x],-1);

	}

}

void DFS1(const ui&u){

	siz[u]=1;d[u]=d[fa[u]]+1;dfn[u]=L[u]=++dfc;

	for(ui v,E(h[u]);E;E=e[E].nx)if((v=e[E].v)^f[u]){

		f[v]=fa[v]=u;DFS1(v);siz[u]+=siz[v];if(siz[v]>siz[Son[u]])Son[u]=v;

	}

	R[u]=dfc;Modify(1,L[u],R[u],1);

}

void DFS2(const ui&u,const ui&tp){

	top[u]=tp;if(!Son[u])return;DFS2(Son[u],tp);

	for(ui E(h[u]);E;E=e[E].nx)if(e[E].v^fa[u]&&e[E].v^Son[u])DFS2(e[E].v,e[E].v);

}

inline ui LCA(ui u,ui v){

	while(top[u]^top[v])d[top[u]]>d[top[v]]?u=fa[top[u]]:v=fa[top[v]];return d[u]>d[v]?v:u;

}

signed main(){

	ui i,x,u,v,opt;scanf("%u%u",&n,&m);

	for(i=1;i<n;++i)scanf("%u%u",&u,&v),Add(u,v);DFS1(1);DFS2(1,1);

	while(m--){

		scanf("%u",&opt);

		if(opt==1)scanf("%u",&u),Access(u);

		if(opt==2){

			scanf("%u%u",&u,&v);x=LCA(u,v);

			printf("%u\n",Query(1,dfn[u],dfn[u])+Query(1,dfn[v],dfn[v])-2*Query(1,dfn[x],dfn[x])+1);

		}

		if(opt==3)scanf("%u",&u),printf("%u\n",Query(1,L[u],R[u]));

	}

}

巴特西

LGP3703题解

最新文章

热门文章