题目大意
题目分析
我们可以用两次树形动规预处理出安全系数Si
方法就是先用一次Dp求出子树的最长距离以及子树的次长距离。
再用一次Dp求出来自父亲的距离，要注意排开自身信息（不能把自己的信息再从父亲传下来），故要记录$From[i]$表示$i$的最长距离来自哪边。
然后用Sparse_Table稀疏表预处理出$k$倍祖先与$k$倍祖先路径上的安全系数最大值。
对于路径$x\rightarrow y$我们分为从$x\rightarrow lca$的左链与$lca\rightarrow y$的右链。
对于左链我们需要完成的任务是：寻找安全系数大于给定值的最靠近$x$的点。
我们只需要在满足不存在路径上最大值大于给定值的范围内不断倍增即可找到最大值。
若在左链没有找到答案，我们仍需要在右链寻找答案。
对于右链我们需要完成的任务是：寻找安全系数大于给定值的最靠近$lca$的点，也就是最远离$y$的点。
我们使用普通的倍增是无法处理这样的问题的，我们可以转化为二分长度+判断是否存在可行解。（如图）
我们二分出来一个限定长度，判断是否在该限定长度是否有一个满足条件的点，若不存在将长度放大，否则将长度缩小，这样我们便可以完成右链的询问。
时间复杂度$O(m\log^2n)$，需要卡卡常数。
xinyue给出了一种$O(m\log n)$，右链不需要二分，我们将右链拆成一半，若在上半部分递归找到了解，那么直接返回，否则在下半部分倍增寻找解。（实际上还是一种折半递归的思想）
因为$T(n)=T(\frac{n}{2})+log(n)=O(\log n)$，因此总时间复杂度是$O(m\log n)$的。
代码
并没有使用xinyue的方法。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
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL 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;
struct Edge {
int from,to,dist;
};
vector<Edge>edges[maxn];
LL f[maxn],g[maxn];
int a,b,c,Max[maxn][35];
int n,m,father[maxn],Depth[maxn],From[maxn],p[maxn][35];
void AddEdge(int x,int y,LL v) {
edges[x].push_back((Edge) {
x,y,v
});
}
void TreeDp1(int Now,int fa,int depth) {
father[Now]=fa;
Depth[Now]=depth;
for(int i=0; i<edges[Now].size(); i++) {
Edge& e=edges[Now][i];
int Next=e.to;
if(Next==fa)continue;
TreeDp1(Next,Now,depth+1);
if(f[Next]+e.dist>f[Now]) {
g[Now]=f[Now];
f[Now]=f[Next]+e.dist;
From[Now]=Next;
} else if(f[Next]+e.dist>g[Now])g[Now]=f[Next]+e.dist;
}
}
void TreeDp2(int Now,int fa,int d) {
if(fa) {
if(From[fa]!=Now&&f[fa]+d>=f[Now]) {
g[Now]=f[Now];
f[Now]=f[fa]+d;
From[Now]=fa;
}
if(From[fa]!=Now&&f[fa]+d>=g[Now])g[Now]=f[fa]+d;
if(From[fa]==Now&&g[fa]+d>=f[Now]) {
g[Now]=f[Now];
f[Now]=g[fa]+d;
From[Now]=fa;
}
if(From[fa]==Now&&g[fa]+d>=g[Now])g[Now]=g[fa]+d;
}
for(int i=0; i<edges[Now].size(); i++) {
Edge& e=edges[Now][i];
int Next=e.to;
if(Next==fa)continue;
TreeDp2(Next,Now,e.dist);
}
}
void Sparse_Table() {
for(int i=1; i<=n; i++)
for(int j=0; j<=log2(n); j++)
p[i][j]=-1;
for(int i=1; i<=n; i++)p[i][0]=father[i];
for(int j=1; j<=log2(n); j++)
for(int i=1; i<=n; i++)
if(p[i][j-1]!=-1) {
p[i][j]=p[p[i][j-1]][j-1];
Max[i][j]=max(Max[i][j-1],Max[p[i][j-1]][j-1]);
}
}
int LCA(int a,int b) {
if(Depth[a]<Depth[b])swap(a,b);
int k=log2(Depth[a]);
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;
k=log2(Depth[a]);
for(int i=k; i>=0; i--)
if(p[a][i]!=-1&&p[a][i]!=p[b][i]) {
a=p[a][i];
b=p[b][i];
}
return p[a][0];
}
int Solve1(int x,int lca,LL v) {
if(Max[x][0]>=v)return x;
int k=log2(Depth[x]);
for(int i=k; i>=0; i--)
if(Depth[x]-(1<<i)>=Depth[lca]&&Max[x][i]<v)x=p[x][i];
if(Max[x][0]>=v)return x;
else return -1;
}
int Solve2(int x,int lca,LL v,int len) {
int k=log2(Depth[x]);
for(int i=k; i>=0; i--)
if(Depth[x]-(1<<i)>=Depth[lca]+len)x=p[x][i];
k=log2(Depth[x]);
for(int i=k; i>=0; i--)
if(Depth[x]-(1<<i)>=Depth[lca]&&Max[x][i]>=v)return true;
else if(Depth[x]-(1<<i)>=Depth[lca])x=p[x][i];
return false;
}
int Solve2(int x,int lca,LL v) {
int Left=0,Right=Depth[x]-Depth[lca];
while(Left<=Right) {
int mid=(Left+Right)>>1;
if(Solve2(x,lca,v,mid))Right=mid-1;
else Left=mid+1;
}
if(Left==Depth[x]-Depth[lca]+1)return -1;
int k=log2(Depth[x]);
for(int i=k; i>=0; i--)
if(Depth[x]-(1<<i)>=Depth[lca]+Left)x=p[x][i];
return x;
}
int main() {
n=Get_Int();
m=Get_Int();
a=Get_Int();
b=Get_Int();
c=Get_Int();
for(int i=1; i<n; i++) {
LL x=Get_Int(),y=Get_Int(),v=Get_Int();
AddEdge(x,y,v);
AddEdge(y,x,v);
}
TreeDp1(1,0,1);
TreeDp2(1,0,0);
for(int i=1; i<=n; i++)Max[i][0]=(LL)(f[i]+a)*b%c;
Sparse_Table();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
LL v=Get_Int();
int lca=LCA(x,y);
int ans=Solve1(x,lca,v);
if(ans==-1)ans=Solve2(y,lca,v);
printf("%d\n",ans);
}
return 0;
}
