GGAutomaton's Blog
0%

斐波那契树（动态点分治）

发表于 分类于 ，

本题谢绝转载

五十分很送，七十分也水。

斐波那契数列有两个性质：
1.两个斐波那契数列相加，还是斐波那契数列。
2.斐波那契数列断开，还是斐波那契数列。

一个点的权值，只与首项的值（也就是起点的a和b，但是这个点的权值只表现出a）以及首项到它的距离有关。
对于70分，首项位置确定，它到所有点的距离可以预处理。
只需要维护首项的值，建立两个树状数组，下标是到起点的距离+1（因为update(0,val)以及其他一些东西会出现问题，所以下标统统+1），值是a和b。修改时在1加a加b，在m+2减a减b。询问时getsum(dist+1)即可得到首项。

对于100分，用出题者的话说，“不停地换点做修改，很明显是点分治啦”。
于是，动态点分治。
每一次在点分树往上爬，相当于把斐波那契数列截断，算出新的首项和距离在该点更新。为了避免重复计算，需要记录是从哪个方向爬过来的，新开树状数组计算重复，询问时减掉即可。
询问就是在该点往上爬，算出它自己以及点分树上它的父亲对它的影响。

后话：
自学了点分治，前前后后花了一个多星期的零散时间写这道题。
修了各种bug，研究vector数组套结构体vector。
顺便试了一下类似于RMQ求LCA的东西。原理：https://www.cnblogs.com/scau20110726/archive/2013/05/26/3100812.html
打出了有史以来最长的代码，下面附的还是精简版。

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
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
const int Mod=1e9+7;
struct BIT {
	int size;
	vector<LL> c1,c2;
	inline void init(int dist) {
		size=dist+1;
		c1.resize(size+1);
		c2.resize(size+1);
	}
	inline int lowbit(int x) {
		return x&-x;
	}
	inline void update(int x,LL val1,LL val2) {
		if (val1<0) val1+=Mod;
		if (val2<0) val2+=Mod;
		for (;x<=size;x+=lowbit(x)) {
			c1[x]+=val1;c2[x]+=val2;
			if (c1[x]>=Mod) c1[x]-=Mod;
			if (c2[x]>=Mod) c2[x]-=Mod;
		}
	}
	inline void getsum(int x,LL &a,LL &b) {
		a=b=0;
		for (;x;x-=lowbit(x)) {
			a+=c1[x];b+=c2[x];
			if (a>=Mod) a-=Mod;
			if (b>=Mod) b-=Mod;
		}
	}
};
vector<BIT> node[200005];
int head[200005],vet[400005],nxt[400005],num;
int Dep[200005],R[400005],F[200005],st[400005][19],ti,pow2[19];
int sz[200005],mxs[200005],root,mxson;
int fa[200005],idx[200005];
LL fib1[200005],fib2[200005];
bool vis[200005];
int n,q;
void addedge(int x,int y) {
	num++;vet[num]=y;nxt[num]=head[x];head[x]=num;
	num++;vet[num]=x;nxt[num]=head[y];head[y]=num;
}
inline int read() {
	char ch=0;int sum=0;
	while (ch<'0' || ch>'9') ch=getchar();
	while (ch<='9' && ch>='0') sum=sum*10+ch-'0',ch=getchar();
	return sum;
}
void dfs(int x,int dep,int ff) {
	Dep[x]=dep;
	R[++ti]=dep;
	F[x]=ti;
	for (int e=head[x];e;e=nxt[e]) {
		if (vet[e]==ff) continue;
		int v=vet[e];
		dfs(v,dep+1,x);
		R[++ti]=dep;
	}
}
void ST(int len) {
	int K=(int)(log((double)len)/log(2.0));
	for (int i=1;i<=len;i++) st[i][0]=R[i];
	for (int i=1;i<=K;i++) {
		for (int j=1;j+pow2[i]-1<=len;j++) {
			st[j][i]=min(st[j][i-1],st[j+pow2[i-1]][i-1]);
		}
	}
}
int getdist(int u,int v) {
	int x=F[u],y=F[v];
    if (x>y) swap(x,y);
	int K=(int)(log((double)y-x+1)/log(2.0));
	return Dep[u]+Dep[v]-2*min(st[x][K],st[y-pow2[K]+1][K]);
}

void getroot(int x,int ff,int tt) {
    sz[x]=1;mxs[x]=0;
    for (int e=head[x];e;e=nxt[e]) {
        int v=vet[e];
        if (v==ff || vis[v]) continue;
        getroot(v,x,tt);
        sz[x]+=sz[v];
        mxs[x]=max(mxs[x],sz[v]);
    }
    mxs[x]=max(mxs[x],tt-sz[x]);
    if (mxs[x]<mxs[root]) root=x,mxson=mxs[x];
}
void solve(int x,int tot) {
    vis[x]=true;int son=0,mx=mxson;
    for (int e=head[x];e;e=nxt[e]) {
        if (!vis[vet[e]]) {
            root=0;
            int tt=sz[vet[e]];
            if (tt>sz[x]) tt=tot-sz[x];
            getroot(vet[e],x,tt);
            fa[root]=x;
            idx[root]=++son;
            solve(root,tt);
        }
    }
    node[x].resize(son+1);
    if (!son) {
    	node[x][0].init(0);
    	return;
	}
	for (int i=0;i<=son;i++) node[x][i].init(mx);
}
inline LL getfib(LL a,LL b,int dist) {
	return (fib1[dist]*a+fib2[dist]*b)%Mod;
}
inline void modify(int x,int m,LL a,LL b) {
	int u=x,ff=fa[u];
	node[u][0].update(1,a,b);
	if (node[u][0].size>=m+2) {
		node[u][0].update(m+2,-a,-b);
	}
	while (ff) {
		int dist=getdist(x,ff);
		if (dist<=m) {
			LL tmp1=getfib(a,b,dist),tmp2=getfib(a,b,dist+1);
			dist=m-dist;
			node[ff][0].update(1,tmp1,tmp2);
			node[ff][idx[u]].update(1,tmp1,tmp2);
			if (dist+2<=node[fa[u]][0].size) {
				node[ff][0].update(dist+2,-tmp1,-tmp2);
				node[ff][idx[u]].update(dist+2,-tmp1,-tmp2);
			}
		}
		u=ff;
		ff=fa[u];
	}
}
inline LL query(int x) {
	int u=x,ff=fa[u];
	LL ans=node[u][0].c1[1],a=0,b=0;
	while (ff) {
		int dist=getdist(x,ff);
		if (dist<node[ff][0].size) {
			node[ff][0].getsum(dist+1,a,b);
			ans+=getfib(a,b,dist);
			if (ans>=Mod) ans-=Mod;
			node[ff][idx[u]].getsum(dist+1,a,b);
			ans-=getfib(a,b,dist);
			if (ans<0) ans+=Mod;
		}
		else cout<<"ERROR\n";
		u=ff;
		ff=fa[u];
	}
	return ans;
}
int main() {
	freopen("fibtree.in","r",stdin);
	freopen("fibtree.out","w",stdout);
	n=read();q=read();
	for (int i=1;i<n;i++) {
		int x=read(),y=read();
		addedge(x,y);
	}
	
	pow2[0]=1;
	for (int i=1;i<=18;i++) pow2[i]=pow2[i-1]<<1;
	dfs(1,1,0);
	ST(n*2-1);
	fib1[0]=1;fib2[1]=1;
	for (int i=2;i<=n;i++) {
		fib1[i]=fib1[i-1]+fib1[i-2];
		if (fib1[i]>=Mod) fib1[i]-=Mod;
		fib2[i]=fib2[i-1]+fib2[i-2];
		if (fib2[i]>=Mod) fib2[i]-=Mod;
	}
	
	mxs[0]=(n<<1);root=0;
    getroot(1,0,n);
    solve(root,n);
	
	for (int i=1;i<=q;i++) {
		int op=read(),u=read();
		if (op==1) {
			int m=read(),a=read(),b=read();
			modify(u,m,a,b);
		}
		else {
			printf("%lld\n",query(u));
		}
	}
	return 0;
}

只是对拍了一下，正确性不能保证，但应该没问题。