BZOJ2759 一个动态树好题

发表于 | 更新于

题意

给定同余方程组xi≡kixpi+bix_i \equiv k_ix_{p_i}+b_i，要求支持如下操作

  • 输出xix_i
  • 修改一个方程

做法

从四月开始学LCT就想做的题目，现在总算A掉了十分欣慰。中秋节假期完成了一项遗愿。。 每个方程看做一个节点i，将i与p_i连边即可形成一个基环森林 基环树的形态是一个链在端点上连着一个环
由于要支持修改操作，即在树上换爹的操作，所以要用LCT 因为要用LCT，所以要拆环，每个点记录virtual father表示拆环之前的father，这样，每棵基环树上有一个vfa不为null的节点，自然该点为root,将vfa称为断点。 现在要维护信息。可以发现环上的每个点转一圈都可以得到与自己的形如x≡kx+bx \equiv kx+b的线性关系。只要找出一个点的这个方程，解出来，那基环树上所有的点就都搞定了。 这样，因为断点一定在环上，而且貌似比较特殊，所以就想办法维护断点的方程。 

1
2
Access(vfa);
Splay(vfa);

这样，从vfa向上，一直到root的点就都在左子树。valup()valup()的时候就把左子树的方程带入自己得到，再把左子树带入自己的方程带入右子树的方程就行了。

TIPS

  • 同一时刻，每个节点维护的信息不需要都有什么意义，因为获得信息的时候要Access+SplayAccess+Splay。需要考虑的只是怎么样动态的得到根节点的信息，让根节点的信息有意义即可。
  • 基环树形态的特殊性使其可以用树上的结构处理。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <cctype>
using std::pair;
using std::make_pair;
inline void read(int &x)
{
	char ch=0;
	int f=1;
	while(!isdigit(ch=getchar()))
		if(ch=='-') f=-1;
	x=ch-'0';
	while(isdigit(ch=getchar()))
		x=x*10+ch-'0';
	x*=f;
}
inline void read(char &ch)
{
	while(!isupper(ch=getchar()));
}
const int MAXN=30000+1;
const int P=10007;
pair<int,int> Exgcd(int a,int b)
{
	if(!b)
		return make_pair(1,0);
	else
	{
		pair<int,int> res=Exgcd(b,a%b);
		return make_pair(res.second,res.first-a/b*res.second);
	}
}
inline int Inv(int x)//MOD p相等的数字逆元相等
{
	int res=Exgcd((x+P)%P,P).first;
	return (res%P+P)%P;
}
struct Line
{
	int k,b;
	Line(int _k=1,int _b=0)
	{
		k=_k;
		b=_b;
	}
	inline int At(int pos)
	{
		return ((k*pos+b)%P+P)%P;
	}
};
inline void cat(Line& a,const Line& b)//b带入a
{
	a.b+=a.k*b.b;
	a.k*=b.k;
	a.b%=P;
	a.k%=P;
}
struct SplayNode
{
	SplayNode *son[2],*fa,*vfa;
	Line sef,suv;
	inline bool isRoot()
	{
		return fa->son[0]!=this && fa->son[1]!=this;
	}
	inline SplayNode *Root()
	{
		return fa->son[0]==fa?this:fa->Root();
	}
	inline int kind()
	{
		return fa->son[1]==this;
	}
	inline void valup()
	{
		suv=son[1]->suv;
		cat(suv,sef);
		cat(suv,son[0]->suv);
	}
}spl[MAXN],*pc=&spl[0],*T[MAXN],*null=&spl[0];
inline void trans(SplayNode *pos)
{
	SplayNode *f=pos->fa,*grf=f->fa;
	int jud=pos->kind();
	if(!f->isRoot())
		grf->son[f->kind()]=pos;
	pos->fa=grf;
	
	f->son[jud]=pos->son[!jud];pos->son[!jud]->fa=f;
	pos->son[!jud]=f;f->fa=pos;

	f->valup();
	pos->valup();
}
inline void Splay(SplayNode *pos)
{
	SplayNode *f;
	while(!pos->isRoot())
	{
		f=pos->fa;
		if(!f->isRoot())
			trans(f->kind()==pos->kind()?f:pos);
		trans(pos);
	}
}
inline void Access(SplayNode *pos)
{
	SplayNode *pred=null;
	while(pos!=null)
	{
		Splay(pos);
		pos->son[1]=pred;
		pos->valup();
		pred=pos;
		pos=pos->fa;
	}
}
void out(SplayNode *pos)
{
	if(pos==null)
		return;
	out(pos->son[0]);
	printf("%x ",pos);
	out(pos->son[1]);
}
int o(SplayNode *pos)
{
	while(!pos->isRoot())
		pos=pos->fa;
	out(pos);puts("");
}
inline SplayNode *Low(SplayNode *pos)
{
	/*while(!pos->isRoot())
		pos=pos->fa;
	*/
	Access(pos);

	Splay(pos);
	while(pos->son[0]!=null)
		pos=pos->son[0];
	return pos;
}
inline SplayNode *newnode(int k,int b)
{
	++pc;
	pc->sef=pc->suv=Line(k,b);
	pc->son[0]=pc->son[1]=pc->fa=pc->vfa=null;
	return pc;
}
int Que(int x)
{
	SplayNode *pos=T[x],*low=Low(pos),*vf=low->vfa;
	Access(vf);
	Splay(vf);
	Line f_vf=vf->suv;
	Access(pos);
	Splay(pos);
	Line f_pos=pos->suv;
	if(f_vf.b==0)
		return f_vf.k==1?-2:-1;
	else if(f_vf.k==0)
		return f_pos.At(f_vf.b);
	else
	{
		int re=-f_vf.b*Inv(f_vf.k-1);
		re=(re%P+P)%P;
		return f_pos.At(re);//144 行应该不用mod 在这里边会mod
	}
}
int Modify(int x,int k,int p,int b)
{
	SplayNode *pos=T[x];
	
	Access(pos);
	Splay(pos);

	pos->sef=Line(k,b);
	pos->valup();
	//cut
	if(pos->vfa!=null)
		pos->vfa=null;
	else
	{
		SplayNode *low=Low(pos);
		pos->son[0]->fa=null;
		pos->son[0]=null;
		pos->valup();
		if(low->Root()!=low->vfa->Root())
		{
			Access(low);
			Splay(low);
			low->fa=low->vfa,low->vfa=null;
		}
	}
	//link
	Access(pos);
	Splay(pos);
	if(pos->Root()==T[p]->Root())
		pos->vfa=T[p];
	else
		pos->fa=T[p];
}
int main()
{
	null->son[0]=null->son[1]=null;

	null->fa=null;

	//freopen("input.txt","r",stdin);
	int n;read(n);
	int t1,t2,t3,t4;
	int tf[MAXN];
	for(int i=1;i<=n;i++)
	{
		read(t1),read(tf[i]),read(t3);
		T[i]=newnode(t1,t3);
	}
	for(int i=1;i<=n;i++)
	{
		if(T[i]->Root()==T[tf[i]]->Root())
			T[i]->vfa=T[tf[i]];
		else
			T[i]->fa=T[tf[i]];
	}
	int m;read(m);
	char opt;
	for(int i=1;i<=m;i++)
	{
		read(opt);
		if(opt=='A')
		{
			read(t1);
			printf("%d\n",Que(t1));
		}
		else
		{
			read(t1),read(t2),read(t3),read(t4);
			Modify(t1,t2,t3,t4);
		}
	}

	return 0;
}