【bzoj2759】一个动态树好题

  • 恭喜你发现了一道真·动态树好题！

显然，根据P的关系完成建图之后，我们得到了一个外向环基森林，其中每个节点都与父亲满足一个线性关系

按照环基树的处理方法，拆掉环上一条边，将其置为$special_father$（简称$spf$），用$link_cut_tree$维护森林即可

如下图所示：

接下来我们考虑两个节点的合并：

$x_1 \equiv k_1 x_2+b_1　(mod 10007)$

$x_2 \equiv k_2 x_3+b_2　(mod 10007)$

合并得到：$x_1 \equiv k_1 k_2 x_3+k_1 b_2+b_1　(mod 10007)$

所以$access(x),splay(x)$即可得到$x$与$Spf$的线性关系

然后$access(s),splay(s)$得到$Spf$与自身的线性关系

注意：一步合并操作之后得到的是该节点的父亲与该节点的线性关系

核心操作：$updata(x):sum[x]=sum[son[x][0]]+v[x]+sum[son[x][1]]$（这里的$’+’$指的是合并）

故操作完成后我们得到的是$Spf$节点与自身的线性关系：形如$x \equiv kx+b　(mod 10007)$

(1)若$k=1$,则$b=0$时有无数个解，$b=1$时无解

(2)若$k=0$,解即为$b$

(3)否则，$x \equiv -b(k-1)^(-1)$，乘法逆元求解即可

求解出$Spf$的答案之后，带入$x$节点与$Spf$的线性关系式即可得到$x$节点的解

信息修改操作：$modify(x,k,p,b)$

修改$k,b$的话，只需要$access(x),splay(x)$提取树链直接修改

修改父亲比较麻烦：

(1)若$x$节点在环上，将确定$Spf$时删掉的边连上，然后将$x$的父边删掉，此时$x$暂时变成了根

　　(i)若$x,p$位于同一树中，直接更新$Spf$即可

　　(ii)否则,$spf[x]=0$,同时把该边连上：$linkk(x,p)$

(2)若$x$节点不在环上，删掉父边之后，$x$作为根将子树分离了出来，处理方法同上

由于此题模数较小，使用习惯性的取模方法跑的非常慢，反而直接取模跑的很快

有图为证：

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 30010
const int mod=10007;
int n,Q,K[MAXN],B[MAXN],f[MAXN],dfn[MAXN],vis[MAXN],spf[MAXN],Ni[MAXN],son[MAXN][2];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
inline int add(int a,int b){return (a+b)%mod;}
inline int sub(int a,int b){return (a-b)%mod;}
inline int mul(int a,int b){return (a*b)%mod;}
struct complex{
	int k,b;
	complex(int k=0,int b=0):k(k),b(b){}
	inline complex operator +(complex &y){
		return complex(mul(k,y.k),add(mul(b,y.k),y.b));
	}
	inline int calc(int x){return add(mul(k,x),b);}
}v[MAXN],sum[MAXN];
inline int power(int a,int b){
	int ret(1);
	while(b){
		if(b&1)  ret=mul(ret,a);
		a=mul(a,a);  b>>=1;
	}return ret;
}
class Link_Cut_Tree{
	private:
		inline bool get(int x){return son[f[x]][1]==x;}
		inline bool isroot(int x){return son[f[x]][0]!=x&&son[f[x]][1]!=x;}
		inline void updata(int x){
			sum[x]=v[x];
			if(son[x][0])  sum[x]=sum[son[x][0]]+v[x];
			if(son[x][1])  sum[x]=sum[x]+sum[son[x][1]];
		}
		inline void rotate(int x){
			int y=f[x],z=f[y],which=get(x);
			if(!isroot(y))  son[z][son[z][1]==y]=x;
			son[y][which]=son[x][which^1];  f[son[x][which^1]]=y;
			son[x][which^1]=y;  f[y]=x;  f[x]=z;
			updata(y);  updata(x);
		}
		inline void splay(int x){
			for(int y=f[x];!isroot(x);rotate(x),y=f[x])
				if(!isroot(y))  rotate(get(x)==get(y)?y:x);
		}
		inline void access(int x){
			int last(0);
			while(x){
				splay(x);
				son[x][1]=last;
				updata(x);
				last=x; x=f[x];
			}
		}
		inline void linkk(int x,int y){
			access(x);  splay(x);  f[x]=y;
		}
		inline void cut(int x){
			access(x);  splay(x);  f[son[x][0]]=0;  son[x][0]=0;  updata(x);
		}
		inline int find(int x){
			access(x);  splay(x);  
			while(son[x][0])  x=son[x][0];  
			splay(x);
			return x;
		}
		inline bool On_Circle(int x,int root){
			int f=spf[root];
			if(f==x)  return 1;
			access(f);  splay(f);  splay(x);
			return !isroot(f);
		}
	public:
		int query(int x){
			access(x);  splay(x);  complex v1=sum[x];
			int root=find(x),f=spf[root];
			access(f);  splay(f);  complex v2=sum[f];
			if(v2.k==1)  return v2.b?-1:-2;
			if(v2.k==0)  return v1.calc(v2.b);
			return v1.calc(sub(mod,mul(v2.b,Ni[v2.k-1])));
		}
		void solve(int x,int k,int p,int b){
			access(x);  splay(x);  v[x]=sum[x]=complex(k,b); updata(x);
			int root1=find(x);
			if(x==root1){
				if(find(p)==x)  spf[x]=p;
				else spf[x]=0,linkk(x,p);
			}
			else if(On_Circle(x,root1)){
				cut(x);  linkk(root1,spf[root1]);  spf[root1]=0;
				if(find(p)==x)  spf[x]=p;
				else linkk(x,p);
			}
			else{
				cut(x);
				if(find(p)==x)  spf[x]=p;
				else linkk(x,p);
			}
		}
}Tree;
void dfs(int x){
	int y=f[x];  dfn[x]=vis[x]=1;
	if(dfn[y])  spf[x]=y,f[x]=0;
	if(!vis[y])  dfs(f[x]);
	dfn[x]=0;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();
	for(int i=1;i<=n;++i)  K[i]=read(),f[i]=read(),B[i]=read();
	for(int i=1;i<=n;++i)  v[i]=sum[i]=complex(K[i],B[i]);
	for(int i=1;i<=n;++i)  if(!vis[i])  dfs(i);
	for(int i=1;i<=n;++i)  Ni[i]=power(i,mod-2);
	Q=read();
	for(int i=1;i<=Q;++i){
		char ch[5];  scanf("%s",ch);
		if(ch[0]=='A'){
			int x=read();
			printf("%d\n",Tree.query(x));
		}
		else if(ch[0]=='C'){
			int a=read(),k=read(),p=read(),b=read();
			Tree.solve(a,k,p,b);
		}
	}
	return 0;
}

本文标题:【bzoj2759】一个动态树好题

文章作者:chty

发布时间:2018年03月22日 - 21时20分

最后更新:2018年07月25日 - 21时24分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,