【SDOI2017】树点染色【线段树+LCT】

本来只是想练练LCT，没想到是个线段树

对于操作1：诶新的颜色？这不是access吗？

也就是说，我们用一棵splay来表示一种颜色

操作2直接在LCT上乱搞……

不对啊，操作3要查子树

诶好像是静态的

那可以考虑线段树维护dfs序

现在要考虑怎么维护权值

我们发现开始的时候权值就是节点的深度

而在且只在access的时候会改变权值

试试魔改access？

原来：

for (int y=0;x;y=x,x=fa[x])

{

    splay(x);

    ch[x][1]=y;

    update(x);

}

那么主要就是\(ch[x][1]=y\)

实际上这句话包含两个操作：清除\(ch[x][1]\),把\(y\)接到\(x\)的右儿子

清除\(ch[x][1]\),相当于把原来的重边断开

我们只考虑当前这个点改了之后的影响

注意既然他们是重边连起来的，他们原来一定是同色的

而改了之后他们就不同了，所以y的子树权值都会增加1

并且他也不会和这条到根路径上任何一个出现过的颜色相同

同样，把\(y\)接到\(x\)的右儿子，意味着x和y同色了，而原来是不同的，所以y的子树权值都会减少1

线段树维护一下就好

操作2直接单点查询，类似树上前缀和就可以了

于是乎，LCT40多行……

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cctype>

#define MAXN 1000005

#define MAXM 2000005

using namespace std;

inline int read()

{

	int ans=0;

	char c=getchar();

	while (!isdigit(c)) c=getchar();

	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();

	return ans;

}

struct edge

{

	int u,v;

}e[MAXM];

int head[MAXN],nxt[MAXM],cnt;

void addnode(int u,int v)

{

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

	nxt[cnt]=head[u];

	head[u]=cnt;

}

int dep[MAXN],fa[MAXN],up[MAXN][20];

int dfn[MAXN],pos[MAXN],tim,end[MAXN];

void dfs(int u)

{

	dfn[u]=++tim;

	pos[tim]=u;

	for (int i=1;i<20;i++)

		up[u][i]=up[up[u][i-1]][i-1];

	for (int i=head[u];i;i=nxt[i])

		if (!dep[e[i].v])

		{

			dep[e[i].v]=dep[u]+1;

			up[e[i].v][0]=u;

			fa[e[i].v]=u;

			dfs(e[i].v);

		}

	end[u]=tim;

}

int lca(int x,int y)

{

	if (dep[x]<dep[y]) swap(x,y);

	int t=dep[x]-dep[y];

	for (int i=0;(1<<i)<=t;i++)

		if (t&(1<<i))

			x=up[x][i];

	if (x==y) return x;

	for (int i=19;i>=0;i--)

		if (up[x][i]!=up[y][i])

			x=up[x][i],y=up[y][i];

	return up[x][0];

}

namespace SGT

{

	#define lc p<<1

	#define rc p<<1|1

	struct SegmentTree

	{

		int l,r;

		int lazy;

		int mx;

	}t[MAXN<<2];

	void pushup(int p){t[p].mx=max(t[lc].mx,t[rc].mx);}

	void pushlazy(int p,int v){t[p].mx+=v,t[p].lazy+=v;}

	void pushdown(int p)

	{

		if (t[p].lazy)

		{

			pushlazy(lc,t[p].lazy);

			pushlazy(rc,t[p].lazy);

			t[p].lazy=0;

		}

	}

	void build(int p,int l,int r)

	{

		t[p].l=l,t[p].r=r;

		if (l==r){t[p].mx=dep[pos[l]];return;}

		int mid=(l+r)>>1;

		build(lc,l,mid),build(rc,mid+1,r);

		pushup(p);

	}

	void modify(int p,int l,int r,int v)

	{

		if (l<=t[p].l&&t[p].r<=r) return pushlazy(p,v);

		if (r<t[p].l||t[p].r<l)	return;

		pushdown(p);

		if (l<=t[lc].r)	modify(lc,l,r,v);

		if (t[rc].l<=r)	modify(rc,l,r,v);

		pushup(p);

	}

	int querymax(int p,int l,int r)

	{

		pushdown(p);

		if (l<=t[p].l&&t[p].r<=r) return t[p].mx;

		if (r<t[p].l||t[p].r<l) return 0;

		int ans=0;

		if (l<=t[lc].r)	ans=max(ans,querymax(lc,l,r));

		if (t[rc].l<=r)	ans=max(ans,querymax(rc,l,r));

		return ans;

	}

	int query(int p,int k)

	{

		pushdown(p);

		if (t[p].l==t[p].r) return t[p].mx;

		if (k<=t[lc].r) return query(lc,k);

		else return query(rc,k);

	}

}

using namespace SGT;

namespace Splay

{

	int ch[MAXN][2];

	bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}

	int get(int x){return ch[fa[x]][1]==x;}

	void rotate(int x)

	{

		int y=fa[x],z=fa[y];

		int l=get(x),r=l^1;

		int w=ch[x][r];

		if (!isroot(y))	ch[z][get(y)]=x;

		ch[x][r]=y,ch[y][l]=w;

		if (w) fa[w]=y;

		fa[y]=x,fa[x]=z;

	}

	void splay(int x)

	{

		while (!isroot(x))

		{

			int y=fa[x];

			if (!isroot(y))

			{

				if (get(x)==get(y))	rotate(y);

				else rotate(x);

			}

			rotate(x);

		}

	}

}

using namespace Splay;

namespace LCT

{

	int findroot(int x){while (ch[x][0]) x=ch[x][0];return x;}

	void access(int x)

	{

		int w;

		for (int y=0;x;y=x,x=fa[x])

		{

			splay(x);

			if (ch[x][1]){w=findroot(ch[x][1]),modify(1,dfn[w],end[w],1);}

			if (ch[x][1]=y){w=findroot(y),modify(1,dfn[w],end[w],-1);}

		}

	}

}

using namespace LCT;

int main()

{

	int n,m;

	n=read(),m=read();

	for (int i=1;i<n;i++)

	{

		int u,v;

		u=read(),v=read();

		addnode(u,v),addnode(v,u);

	}

	dep[1]=1;

	dfs(1);

	build(1,1,n);

	while (m--)

	{

		int op,x,y,l;

		op=read(),x=read();

		int ans;

		switch(op)

		{

			case 1:access(x);break;

			case 2:

				y=read();

				l=lca(x,y);

				ans=query(1,dfn[x]);

				ans+=query(1,dfn[y]);

				ans-=(query(1,dfn[l])<<1);

				printf("%d\n",ans+1);

				break;

			case 3:

				printf("%d\n",querymax(1,dfn[x],end[x]));

		}

	}

	return 0;

}

巴特西

【SDOI2017】树点染色【线段树+LCT】

最新文章

热门文章