「SDOI2017」树点涂色

我sb的不行了

其实一开始有一个类似动态dp的想法

每个点维护到lct树上到最浅点的颜色段数，然后维护一个\(mx_{0,1}\)也就是是否用虚儿子的最大颜色

用个set维护一下虚儿子

但是啊，我发现搞这个区间改颜色的时候，虚儿子好像得用树套树维护，我当场就不行了...

每个点如果维护到根的颜色段数\(f\)

然后发现啊，这个你如果用一个lct的一个子树维护同一种颜色，在你access的时候实变虚或者虚变实对子树有一个+1或者-1

然后额外在外面开一个线段树维护子树加减，每次access的时候操作

然后这个颜色段比较特殊，链的颜色个数可以\(f_u+f_v-f_{lca(u,v)}*2+1\)，这个简单讨论一下就好了

操作3就是区间最大值

Code:

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

using std::max;

template <class T>

void read(T &x)

{

	x=0;char c=getchar();

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

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

const int N=1e5+10;

int n,m;

int head[N],to[N<<1],Next[N<<1],cnt;

void add(int u,int v)

{

    to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;

}

int mx[N<<2],tag[N<<2];

int dfn[N],low[N],dep[N],yuy[N],f[20][N],dfsclock;

int LCA(int x,int y)

{

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

	for(int i=18;~i;i--)

		if(dep[f[i][x]]>=dep[y])

			x=f[i][x];

	if(x==y) return x;

	for(int i=18;~i;i--)

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

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

	return f[0][x];

}

void pushdown(int id)

{

    if(tag[id])

    {

        tag[id<<1]+=tag[id];

        tag[id<<1|1]+=tag[id];

        mx[id<<1]+=tag[id];

        mx[id<<1|1]+=tag[id];

        tag[id]=0;

    }

}

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

{

	if(l==r) {mx[id]=yuy[l];return;}

	int mid=l+r>>1;

	build(id<<1,l,mid),build(id<<1|1,mid+1,r);

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

}

void modify(int id,int L,int R,int l,int r,int d)

{

	if(l==L&&r==R)

    {

        mx[id]+=d;

        tag[id]+=d;

        return;

    }

    pushdown(id);

	int Mid=L+R>>1;

	if(r<=Mid) modify(id<<1,L,Mid,l,r,d);

	else if(l>Mid) modify(id<<1|1,Mid+1,R,l,r,d);

	else modify(id<<1,L,Mid,l,Mid,d),modify(id<<1|1,Mid+1,R,Mid+1,r,d);

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

}

int query(int id,int l,int r,int p)

{

	if(l==r) return mx[id];

	pushdown(id);

	int mid=l+r>>1;

	if(p<=mid) return query(id<<1,l,mid,p);

	else return query(id<<1|1,mid+1,r,p);

}

int query(int id,int L,int R,int l,int r)

{

	if(L==l&&R==r) return mx[id];

	pushdown(id);

	int Mid=L+R>>1;

	if(r<=Mid) return query(id<<1,L,Mid,l,r);

	else if(l>Mid) return query(id<<1|1,Mid+1,R,l,r);

	else return max(query(id<<1,L,Mid,l,Mid),query(id<<1|1,Mid+1,R,Mid+1,r));

}

int ch[N][2],par[N],Lef[N];

#define fa par[now]

#define ls ch[now][0]

#define rs ch[now][1]

bool isroot(int now){return ch[fa][0]==now||ch[fa][1]==now;}

int identity(int now){return ch[fa][1]==now;}

void connect(int f,int now,int typ){ch[fa=f][typ]=now;}

void updata(int now)

{

    Lef[now]=now;

    if(ls) Lef[now]=Lef[ls];

}

void Rotate(int now)

{

	int typ=identity(now),p=fa;

	connect(p,ch[now][typ^1],typ);

	if(isroot(p)) connect(par[p],now,identity(p));

	else fa=par[p];

	connect(now,p,typ^1);

	updata(p),updata(now);

}

void splay(int now)

{

	for(;isroot(now);Rotate(now))

		if(isroot(fa))

			Rotate(identity(fa)^identity(now)?now:fa);

}

void access(int now)

{

	for(int las=0;now;las=now,now=fa)

	{

		splay(now);

		if(rs)

            modify(1,1,n,dfn[Lef[rs]],low[Lef[rs]],1);

		if(las)

		    modify(1,1,n,dfn[Lef[las]],low[Lef[las]],-1);

		rs=las;

		updata(now);

	}

}

void dfs(int now,int dis)

{

	dfn[now]=++dfsclock;

	yuy[dfsclock]=dis;

	dep[now]=dep[par[now]=f[0][now]]+1;

	for(int i=1;f[i-1][now];i++) f[i][now]=f[i-1][f[i-1][now]];

	for(int v,i=head[now];i;i=Next[i])

		if((v=to[i])!=f[0][now])

			f[0][v]=now,dfs(v,dis+1);

	low[now]=dfsclock;

}

int main()

{

	read(n),read(m);

 	for(int u,v,i=1;i<n;i++) read(u),read(v),add(u,v),add(v,u);

	dfs(1,1);

	build(1,1,n);

	for(int op,x,y,i=1;i<=m;i++)

	{

		read(op),read(x);

		if(op==1) access(x);

		else if(op==2)

		{

			read(y);

			printf("%d\n",query(1,1,n,dfn[x])+query(1,1,n,dfn[y])-(query(1,1,n,dfn[LCA(x,y)])<<1)+1);

		}

		else

            printf("%d\n",query(1,1,n,dfn[x],low[x]));

	}

	return 0;

}

2019.4.10

巴特西

「SDOI2017」树点涂色解题报告

「SDOI2017」树点涂色

最新文章

热门文章

巴特西

「SDOI2017」树点涂色 解题报告

「SDOI2017」树点涂色

最新文章

热门文章

「SDOI2017」树点涂色解题报告