SPOJ2939 QTREE5（LCT维护子树信息）

QWQ嘤嘤嘤

此题正规题解应该是边分治？？或者是树剖（总之不是LCT）

但是我这里还是把它当成一个LCT题目来做

首先，这个题的重点还是在update上

因为有\(makeroot\)这个操作的存在，所以自然避免不了\(reverse\)，而当\(reverse\)之后，会影响到每个点维护的值的时候，就需要同时维护两个相反的数组，在\(reverse\)的时候，直接\(swap\)

对于本题来说，我们对于一个点需要维护一个虚子树的\(maxdis\) （这里需要\(multiset\)来维护，因为access的时候，涉及到修改的问题）

一个到深度最浅的点的\(ans1\)，到深度最深的点的\(ans2\)，还有一个子\(splay\)的权值和

考虑转移，ans1的转移显然可以由\(ans1[ch[x][0]]\)转移而来（表示左子树内部的路径），其次，他还可以从\(min(fir(s[x]),ans1[ch[x][1]])+val[x]+val[ch[x][0]\)转移而来（表示从右子树或者虚子树开始的一条路径），如果当前点是合法的颜色，那么还可以从当前点开始的一条路径更新\(ans1\)，而\(ans2\)直接全部反过来就好

void update(int x)

{

	if (!x) return;

	sval[x]=sval[ch[x][0]]+sval[ch[x][1]]+val[x];

	ans1[x]=min(ans1[ch[x][0]],min(fir(x),ans1[ch[x][1]])+val[x]+sval[ch[x][0]]);

	ans2[x]=min(ans2[ch[x][1]],min(fir(x),ans2[ch[x][0]])+val[x]+sval[ch[x][1]]);

	//cout<<x<<" "<<ans1[x]<<" "<<ans2[x]<<" "<<sval[x]<<endl;

	if (col[x])

	{

		ans1[x]=min(ans1[x],sval[ch[x][0]]);

		ans2[x]=min(ans2[x],sval[ch[x][1]]);

	}

	//lmn[x]=min(lmn[ls],len[ls]+val[x]+min(w[x],fir(s[x]),lmn[rs]));

    //rmn[x]=min(rmn[rs],len[rs]+min(w[x],fir(s[x]),rmn[ls]+val[x]));

}

其他的话，就是一些小细节了，可以直接看代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<vector>

#include<queue>

#include<cmath>

#include<map>

#include<set>

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 5e5+1e2;

//const int inf = 1e9;

int lubenwei;

int ch[maxn][3];

int inf;

int fa[maxn],rev[maxn],ans1[maxn],ans2[maxn];

int sval[maxn],val[maxn];

int col[maxn];

int n,m;

multiset<int> s[maxn];

int tot;

int st[maxn];

int son(int x)

{

	if (ch[fa[x]][0]==x) return 0;

	else return 1;

}

bool notroot(int x)

{

	return ch[fa[x]][0]==x || ch[fa[x]][1]==x;

}

void reverse(int x)

{

	swap(ans1[x],ans2[x]);

	rev[x]^=1;

	swap(ch[x][0],ch[x][1]);

}

int fir(int x)

{

	//cout<<"ymh"<<endl;

   if (s[x].size()>=1) return *(s[x].begin());

   else return inf;

}

void update(int x)

{

	if (!x) return;

	sval[x]=sval[ch[x][0]]+sval[ch[x][1]]+val[x];

	ans1[x]=min(ans1[ch[x][0]],min(fir(x),ans1[ch[x][1]])+val[x]+sval[ch[x][0]]);

	ans2[x]=min(ans2[ch[x][1]],min(fir(x),ans2[ch[x][0]])+val[x]+sval[ch[x][1]]);

	//cout<<x<<" "<<ans1[x]<<" "<<ans2[x]<<" "<<sval[x]<<endl;

	if (col[x])

	{

		ans1[x]=min(ans1[x],sval[ch[x][0]]);

		ans2[x]=min(ans2[x],sval[ch[x][1]]);

	}

	//lmn[x]=min(lmn[ls],len[ls]+val[x]+min(w[x],fir(s[x]),lmn[rs]));

    //rmn[x]=min(rmn[rs],len[rs]+min(w[x],fir(s[x]),rmn[ls]+val[x]));

}

void pushdown(int x)

{

	if (rev[x])

	{

		if (ch[x][0]) reverse(ch[x][0]);

		if (ch[x][1]) reverse(ch[x][1]);

		rev[x]=0;

	}

}

void rotate(int x)

{

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

	int b=son(x),c=son(y);

	if (notroot(y)) ch[z][c]=x;

	fa[x]=z;

	ch[y][b]=ch[x][!b];

	fa[ch[x][!b]]=y;

    ch[x][!b]=y;

    fa[y]=x;

    update(y);

    update(x);

}

void splay(int x)

{

	int y=x,cnt=0;

	st[++cnt]=y;

	while (notroot(y)) y=fa[y],st[++cnt]=y;

	while (cnt) pushdown(st[cnt--]);

	while (notroot(x))

	{

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

		int b=son(x),c=son(y);

		if (notroot(y))

		{

			if (b==c) rotate(y);

			else rotate(x);

		}

		rotate(x);

	}

	///cout<<2<<endl;

	update(x);

}

void access(int x)

{

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

	{

		splay(x);

	//	cout<<1;

		if (ch[x][1])s[x].insert(ans1[ch[x][1]]);

		if (y && s[x].find(ans1[y])!=s[x].end()) s[x].erase(s[x].find(ans1[y]));

		ch[x][1]=y;

		update(x);

	}

//	cout<<"wancheng";

}

void makeroot(int x)

{

	access(x);//cout<<x<<endl;

	splay(x);

	reverse(x);

}

int findroot(int x)

{

	access(x);

	splay(x);

	while (ch[x][0])

	{

		pushdown(x);

		x=ch[x][0];

	}

	return x;

}

void split(int x,int y)

{

	makeroot(x);

	access(y);

	splay(y);

}

void link(int x,int y)

{

	split(x,y);

	if (findroot(y)!=x)

	{

		fa[x]=y;

		s[y].insert(ans1[x]);

		update(y);

	}

}

int main()

{

	memset(ans1,127/3,sizeof(ans1));

	memset(ans2,127/3,sizeof(ans2));

   inf = ans1[maxn-3];

   n=read();

   lubenwei=0;

   tot=n;

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

   {

   	 int x=read(),y=read();

   	 val[++tot]=1;

   	 link(x,tot);

   	 link(y,tot);

   }

   m=read();

   makeroot(1);

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

   {

   	  int opt=read();

   	  int x=read();

   	  if (opt==0)

   	  {

   	  	makeroot(x);

   	  	col[x]^=1;

   	  	if (col[x]==1) lubenwei++;

   	  	else lubenwei--;

   	  	update(x);

	  }

	  if (opt==1)

	  {

	  	 makeroot(x);

	  	 if (!lubenwei) cout<<-1<<"\n";

	  	 else

	  	 if (col[x]) cout<<0<<"\n";

	  	 else cout<<ans1[x]<<"\n";

	  }

	 // cout<<"6deyanse:"<<col[x]<<endl;

   }

   return 0;

}

巴特西

SPOJ2939 QTREE5（LCT维护子树信息）

最新文章

热门文章