本题最大的难点是小数不容易预处理(容易爆 \(double\))。
考虑如何用整数来表示小数,即 \(w = k\times 10^{-4}\),此时 \(k\) 一定满足 \(k\) 为整数且大于等于零。
因此 \(x\) 和 \(y\) 为端点的简单路径上边权乘积与点 \(x\) 的点权相乘的积可以改写为 \(10^{-4}k_x \times\sum_{i=1}^{i\le num} 10^{-4}k_i\) ,其中 \(\sum_{i=1}^{i\le num} 10^{-4}k_i\) 为简单路径上边权乘积。
改变一下形式:
\[\begin{aligned} &10^{-4}k_x \times\sum_{i=1}^{i\le num} 10^{-4}k_i\\ &10^{-4}k_x \times 10^{-4num}\sum_{i=1}^{i\le num} k_i\\ &10^{-4num-4}\times (k_x \sum_{i=1}^{i\le num} k_i)\\ \end{aligned} \]考虑质因数分解,有 \(k_x \sum_{i=1}^{i\le num} k_i = 2^{c_1}3^{c_2}5^{c_3}\dots p_d^{c_d}\) ,因此该路径上边权乘积与点 \(x\) 的点权相乘的乘积为整数当且仅当 \(4num+4\le c_1,c_3\)。
所以对于每个点记录点权和到 \(1\) 的简单路径上边权乘积的 \(c_1,c_3\) 的值,倍增求 \(LCA\) 就可以在 \(O(n\log n)\) 的复杂度下通过本题。
//Author: __ODT__
// 省略一堆头文件和快读.....
const I inf = 0x3f3f3f3f;
const I N = 1e6;
struct node{
I num2, num5;
void get(){
double s; cin >> s;
I x = (I)((double)s * 10000);
if(x == 0) num2 = num5 = inf;
else{
num2 = -4, num5 = -4;
while(x%2==0)num2++, x/=2;
while(x%5==0)num5++, x/=5;
}
}
void operator += (const node &oth){num2 += oth.num2, num5 += oth.num5;}
node operator - (const node &oth){return (node){num2 - oth.num2, num5 - oth.num5};}
node operator + (const node &oth){return (node){num2 + oth.num2, num5 + oth.num5};}
}a[N];
I n, q;
I h[N], nt[N<<1], to[N<<1], tot;
node val[N<<1];
inl void link(I u, I v){
nt[++tot] = h[u], h[u] = tot, to[tot] = v;
val[tot].get(); swap(u, v);
nt[++tot] = h[u], h[u] = tot, to[tot] = v;
val[tot] = val[tot-1];
}
I st[N][21], dep[N];
node d[N];
inl void dfs(I u, I fa){
st[u][0] = fa, dep[u] = dep[fa] + 1;
for(I i = 1; i <= 18; i ++)
st[u][i] = st[st[u][i-1]][i-1];
for(I i = h[u]; i; i = nt[i]){
I v = to[i];
if(v == fa) continue;
d[v] += val[i];
d[v] += d[u];
dfs(v, u);
}
}
inl I lca(I x, I y){
if(dep[x] < dep[y]) swap(x, y);
for(I i = 18; i >= 0; i --) if(dep[st[x][i]] >= dep[y]) x = st[x][i];
if(x == y){return x;}
for(I i = 18; i >= 0; i --)
if(st[x][i] != st[y][i]) x = st[x][i], y = st[y][i];
return st[x][0];
}
node dist(I x, I y){
I l = lca(x, y);
return a[x] + (d[x] - d[l]) + (d[y] - d[l]);
}
int main(){
n = read(), q = read();
for(I i = 1; i <= n; i ++) a[i].get();
for(I i = 1, u, v; i < n; i ++){
u = read(), v = read(), link(u, v);
}
dfs(1, 0);
for(I i = 1; i <= q; i ++){
I x, y; x = read(), y = read();
node c = dist(x, y);
puts(c.num2 >= 0 && c.num5 >= 0 ? "Yes" : "No");
}
return 0;
}
标签:oth,num5,GROI,node,R1,num2,10,P8972,le
From: https://www.cnblogs.com/dadidididi/p/17069385.html