欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

bzoj2759:一个动态树好题 (LCT+Exgcd)

程序员文章站 2024-02-11 16:44:52
...

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2759

题目分析:这是一道真动态树好题,不像某些其它自称好题的题目(bzoj4300“绝世好题”,其实是大水题)。

言归正传,我们来看看这道题。如果有一条方程是a=ka+b%10007的形式,且0<=a<10007,你会解a吗?很明显,当k=0时,a=b;当k=1时,若b=0,则有无穷多解,否则无解;当k>1时,用扩展欧几里得解。那么假设有两条方程:a1=k1a2+b1%10007,a2=k2a1+b2%10007,你会解a1吗?很简单,我们把前面式子的a2用后面的式子代替,然后就和刚才的一样了。而且这些式子是可以用splay进行信息合并的。

现在题目给出了很多条形如a_i=ki*a_pi+bi%10007的式子,我们认为i的父亲是pi,这样我们就得到了一棵环套树森林,然后我们任意选择一个环上的点i,将i到pi的边断掉,就变成了一个普通的森林,并且我们开一个域special_fa,令Node[i]->special_fa=pi,记录下来:

bzoj2759:一个动态树好题 (LCT+Exgcd)

图中的实边代表树上的边,虚边代表special_fa边。很明显只有一棵树的根,special_fa才会有值。当我们要求a的值的时候,先找到它的根root,然后Access(Node[root]->special_fa),求出Node[root]->special_fa的值,再求出root的值,再通过Access(a),求出a的值。

现在的问题在于修改操作,假设我要改变a的父亲为p,又该怎么做呢?我们先看一下a是否为某棵树的根,是的话就断掉a的special_fa边,然后看一下p是否在a的子树中,是的话a的special_fa变为p,否则a的path_parent变为p;若a不是某棵树的根,先断掉a和它原父亲的边,然后看p是否在a的子树……(同上),最后如果a在原先的环上,还要令a的原根的special_fa边变为path_parent边。(看看上图就可以自己脑补一下了)

擅长数据结构的我这题都调了两个小时(说实话我敲LCT基本上是敲完立马过样例,一交立马AC那种),主要是有些细节一开始没有想清楚,还有码code的时候状态不是很好,出现各种错误。比如说splay信息的合并一开始搞错了;”if (F->fa)”写成了while;我在解扩展gcd的时候,为了避免负数让程序去解Exgcd(M,k-1)而不是1-k,结果最后Y忘了取反;没有判断a是根的情况;修改了k和b的值没有重新再Up()一次;给某个点打path_parent标记之前没有将它Splay等等……QAQ

CODE:

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxn=30010;
const int M=10007;

struct Tnode
{
	int vk,vb,K,B,path_parent,special_fa;
	Tnode *fa,*son[2];
	int Get_d() { return fa->son[1]==this; }
	void Connect(Tnode *P,int d) { (son[d]=P)->fa=this; }
	void Up()
	{
		K=vk,B=vb;
		if (son[0]) B=(K*son[0]->B+B)%M,K=K*son[0]->K%M;
		if (son[1]) B=(son[1]->K*B+son[1]->B)%M,K=son[1]->K*K%M;
	}
} tree[maxn];
Tnode *Node[maxn];
int cur=-1;

int X,Y;
int n,q;

Tnode *New_node()
{
	cur++;
	tree[cur].vk=tree[cur].K=0;
	tree[cur].vb=tree[cur].B=0;
	tree[cur].path_parent=tree[cur].special_fa=0;
	tree[cur].fa=tree[cur].son[0]=tree[cur].son[1]=NULL;
	return tree+cur;
}

void Zig(Tnode *P)
{
	int d=P->Get_d();
	Tnode *F=P->fa;
	if (P->son[!d]) F->Connect(P->son[!d],d);
	else F->son[d]=NULL;
	if (F->fa) F->fa->Connect(P, F->Get_d() );
	else P->fa=NULL;
	F->Up();
	P->Connect(F,!d);
	P->path_parent=F->path_parent;
	F->path_parent=0;
}

void Splay(Tnode *P)
{
	while (P->fa)
	{
		Tnode *F=P->fa;
		if (F->fa) ( P->Get_d()^F->Get_d() )? Zig(P):Zig(F);
		Zig(P);
	}
	P->Up();
}

void Down(int x)
{
	Splay(Node[x]);
	Tnode *&tag=Node[x]->son[1];
	if (tag)
	{
		tag->fa=NULL;
		tag->path_parent=x;
		tag=NULL;
		Node[x]->Up();
	}
}

void Access(int x)
{
	Down(x);
	int y=Node[x]->path_parent;
	while (y)
	{
		Down(y);
		Node[y]->Connect(Node[x],1);
		Node[y]->Up();
		Node[x]->path_parent=0;
		x=y;
		y=Node[x]->path_parent;
	}
}

Tnode *Find_root(Tnode *P)
{
	if (!P->son[0]) return P;
	return Find_root(P->son[0]);
}

bool Judge(Tnode *P,int y)
{
	Access(y);
	Splay(Node[y]);
	return Find_root(Node[y])==P;
}

void Link(int x,int y)
{
	Splay(Node[y]);
	Node[y]->path_parent=x;
}

void Exgcd(int a,int b)
{
	if (!b)
	{
		X=1,Y=0;
		return;
	}
	Exgcd(b,a%b);
	int u=Y;
	Y=X-u*(a/b);
	X=u;
}

int Solve(int k,int b)
{
	k--;
	Exgcd(M,k);
	Y*=b;
	Y=-Y;
	Y=(Y%M+M)%M;
	return Y;
}

int main()
{
	freopen("c.in","r",stdin);
	freopen("c.out","w",stdout);
	
	scanf("%d",&n);
	for (int i=1; i<=n; i++) Node[i]=New_node();
	for (int i=1; i<=n; i++)
	{
		int k,p,b;
		scanf("%d%d%d",&k,&p,&b);
		Node[i]->vk=k;
		Node[i]->vb=b;
		Node[i]->Up();
		if ( !Judge(Node[i],p) ) Link(p,i);
		else Node[i]->special_fa=p;
	}
	
	scanf("%d",&q);
	while (q--)
	{
		char c=getchar();
		while ( c!='A' && c!='C' ) c=getchar();
		
		if (c=='A')
		{
			int a;
			scanf("%d",&a);
			
			Access(a);
			Splay(Node[a]);
			Tnode *P=Find_root(Node[a]);
			
			int sfa=P->special_fa;
			Access(sfa);
			Splay(P);
			int k=P->K;
			int b=P->B;
			
			int root;
			if (!k) root=b;
			if (k==1)
			{
				if (b) printf("-1\n");
				else printf("-2\n");
				continue;
			}
			if (k>1) root=Solve(k,b);
			root=(P->vk*root+P->vb)%M;
			
			if (P==Node[a])
			{
				printf("%d\n",root);
				continue;
			}
			
			Access(a);
			Splay(P);
			k=P->son[1]->K;
			b=P->son[1]->B;
			root=(k*root+b)%M;
			printf("%d\n",root);
		}
		
		if (c=='C')
		{
			int a,k,p,b;
			scanf("%d%d%d%d",&a,&k,&p,&b);
			
			Access(a);
			Splay(Node[a]);
			Tnode *P=Find_root(Node[a]);
			
			if (Node[a]==P)
			{
				P->special_fa=0;
				P->vk=k;
				P->vb=b;
				P->Up();
				
				Access(p);
				Splay(Node[p]);
				if ( Find_root(Node[p])==P ) P->special_fa=p;
				else P->path_parent=p;
				continue;
			}
			
			Access(P->special_fa);
			Splay(Node[a]);
			bool flag=(Find_root(Node[a])==P);
			
			Access(a);
			Splay(Node[a]);
			Node[a]->son[0]->fa=NULL;
			Node[a]->son[0]->path_parent=Node[a]->path_parent;
			Node[a]->path_parent=0;
			Node[a]->son[0]=NULL;
			
			Node[a]->vk=k;
			Node[a]->vb=b;
			Node[a]->Up();
			
			if ( Judge(Node[a],p) ) Node[a]->special_fa=p;
			else Node[a]->path_parent=p;
			if ( flag && !Judge(P,p) )
			{
				Splay(P);
				P->path_parent=P->special_fa;
				P->special_fa=0;
			}
		}
	}
	
	return 0;
}