「vijos-bashu」树形杀手 / 「CodeChef TRIPS」Children Trips - 树链分块 | Bill Yang's Blog

「vijos-bashu」树形杀手 / 「CodeChef TRIPS」Children Trips - 树链分块

题目大意

传送门


题目分析

本题大家都是用的论文上的第二种解法:按大小分类讨论,结合暴力和倍增(因为空间复杂度高需要离线,虽然vijos的内存很大但还是MLE),实现出来代码很短,但是实际测试效率很低(我的正经分块终于体现出优势啦~)

使用 邹逍遥《浅谈分块在一类在线问题中的应用》论文中提到的树上分块方法(我称为树链分块)。
我们对每个点处理以$z(z\in[1,\sqrt n])$为步长跳到的第一个点(没有为$-1$),以$z$为最大步长跳到最近的关键点最少需要几步,跳到关键点后$z$余下的步长,通过父亲递推下来,时间复杂度$O(n\sqrt n)$。

对于每一个询问我们从两个点向lca移动,显然这样答案不会变差,但$lca$不一定是关键点,因此最后一段需要暴力。

爬树分为两种爬树,第一种爬树是询问的步长$P\le \sqrt n$时,因为有了预处理,我们每一步可以先跳到关键点,再跳完跳到关键点余下的步长。

当$P\gt\sqrt n$时,直接暴力步长为$P$向上跳,此时可以倍增,也可以不倍增,因为预处理了$\sqrt n$距离的祖先,因此我们依然可以跳$\sqrt n$的长度,然后计算剩下的步长即可。

因为有可能有$z$距离祖先不存在的情况,需要先跳到$z-1$距离祖先再进行跳跃,此时分类讨论很复杂(见代码),所以很难调试。
但是这样的时间复杂度是严格$O(n\sqrt n)$,实际测试中(截止于目前)在vijos上拿了rank 1。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005,maxb=325;
struct Edge {
int from,to,dist;
};
int n,m,q,size,Upkey[maxn],Depth[maxn],Dist[maxn],Size[maxn],Key[maxn],p[maxn][25],Up[maxn][maxb],Jump[maxn][maxb],Remain[maxn][maxb];
vector<Edge>edges[maxn];
void AddEdge(int x,int y,int v) {
edges[x].push_back((Edge) {x,y,v});
}
void Dfs(int Now,int fa,int depth,int dist,int last) {
Depth[Now]=depth;
Dist[Now]=dist;
Size[Now]=1;
p[Now][0]=fa;
for(int i=1; i<=20; i++)
if(~p[Now][i-1])p[Now][i]=p[p[Now][i-1]][i-1];
else break;
if(last)Up[Now][last]=fa;
int pre=-1;
for(int i=last+1; i<=min(size+1,dist); i++)Up[Now][i]=Up[fa][i-last];
for(Edge& e:edges[Now]) {
int Next=e.to;
if(Next==fa)continue;
Dfs(Next,Now,depth+1,dist+e.dist,e.dist);
Size[Now]+=Size[Next];
}
if(depth%size==0&&Size[Now]>size)Key[Now]=1;
}
void Dfs2(int Now,int fa,int upkey) {
if(upkey) {
Upkey[Now]=upkey;
for(int i=2; i<=size+1; i++)
if(Dist[Now]-Dist[upkey]<=i) {
Jump[Now][i]=1;
Remain[Now][i]=i-(Dist[Now]-Dist[upkey]);
} else if(~Up[Now][i]) {
Jump[Now][i]=Jump[Up[Now][i]][i]+1;
Remain[Now][i]=Remain[Up[Now][i]][i];
} else {
Jump[Now][i]=Jump[Up[Now][i-1]][i]+1;
Remain[Now][i]=Remain[Up[Now][i-1]][i];
}
}
for(Edge& e:edges[Now]) {
int Next=e.to;
if(Next==fa)continue;
Dfs2(Next,Now,Key[Now]?Now:upkey);
}
}
int LCA(int a,int b) {
if(Depth[a]<Depth[b])swap(a,b);
int k=20;
for(int i=k; i>=0; i--) {
if(Depth[a]==Depth[b])break;
if(Depth[a]-(1<<i)>=Depth[b])a=p[a][i];
}
if(a==b)return b;
for(int i=k; i>=0; i--)
if(~p[a][i]&&p[a][i]!=p[b][i]) {
a=p[a][i];
b=p[b][i];
}
return p[a][0];
}
int Jump1(int Now,int target,int& remain,int step,int unused) {
if(Now==target) {
remain=unused;
return 0;
}
if(Dist[Now]-Dist[target]<=unused) {
remain=unused-(Dist[Now]-Dist[target]);
return 0;
}
if((!unused||(unused==1&&Up[Now][1]==-1))&&Dist[Now]-Dist[target]<=step) {
remain=step-(Dist[Now]-Dist[target]);
return 1;
}
if(Depth[Upkey[Now]]<Depth[target]) {
if(unused) {
if(~Up[Now][unused])return Jump1(Up[Now][unused],target,remain,step,0);
else if(unused>1)return Jump1(Up[Now][unused-1],target,remain,step,0);
}
if(~Up[Now][step])return Jump1(Up[Now][step],target,remain,step,0)+1;
else return Jump1(Up[Now][step-1],target,remain,step,0)+1;
}
if(unused) {
if(~Up[Now][unused])return Jump1(Up[Now][unused],target,remain,step,0);
else if(unused>1)return Jump1(Up[Now][unused-1],target,remain,step,0);
}
return Jump1(Upkey[Now],target,remain,step,Remain[Now][step])+Jump[Now][step];
}
int Jump2(int Now,int target,int& remain,int step,int unused) {
if(Now==target) {
remain=unused;
return 0;
}
if(Dist[Now]-Dist[target]<=unused) {
remain=unused-(Dist[Now]-Dist[target]);
return 0;
}
if((!unused||(unused==1&&Up[Now][1]==-1))&&Dist[Now]-Dist[target]<=step) {
remain=step-(Dist[Now]-Dist[target]);
return 1;
}
if(unused>=size) {
if(~Up[Now][size])return Jump2(Up[Now][size],target,remain,step,unused-size);
else return Jump2(Up[Now][size-1],target,remain,step,unused-size+1);
} else if(unused) {
if(~Up[Now][unused])return Jump2(Up[Now][unused],target,remain,step,0);
else if(unused>1)return Jump2(Up[Now][unused-1],target,remain,step,1);
}
if(~Up[Now][size])return Jump2(Up[Now][size],target,remain,step,step-size)+1;
else return Jump2(Up[Now][size-1],target,remain,step,step-size+1)+1;
}
int main() {
memset(p,-1,sizeof(p));
memset(Up,-1,sizeof(Up));
n=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
AddEdge(x,y,v);
AddEdge(y,x,v);
}
size=sqrt(n);
Dfs(1,-1,1,0,0);
Dfs2(1,-1,0);
q=Get_Int();
for(int i=1; i<=q; i++) {
int s=Get_Int(),t=Get_Int(),v=Get_Int();
int lca=LCA(s,t),ans=0,remain1=0,remain2=0;
if(v>=size+1) {
ans=Jump2(s,lca,remain1,v,0)+Jump2(t,lca,remain2,v,0);
if(remain1&&remain2&&remain1+remain2>=v)ans--;
} else {
ans=Jump1(s,lca,remain1,v,0)+Jump1(t,lca,remain2,v,0);
if(remain1&&remain2&&remain1+remain2>=v)ans--;
}
printf("%d\n",ans);
}
return 0;
}
本篇文章有用吗?有用还不快点击!
0%