题解：P8972 『GROI-R1』 一切都已过去
ljc2230
·
·
算法·理论
P8972 『GROI-R1』 一切都已过去
题目解析
给出一棵树的边权和点权，求两点之间的各个边和起点的乘积是否为正数。
解题思路
由题目范围可得，如果使用 double 类型将会超空间，所以不使用这个方法。\
因为小数难以进行计算，所以我们用 xsd 数组记录每一条边的小数的位数，在计算的同时将每一条边的边权 w 累乘 10 便于之后进行计算。\
已知每个数都可以写成 \frac{k}{10^x} 的形式，所以我们用 num2 和 num5 记录每条边中因子 2 和 5 的数量。\
那么如何算出两个点的乘积呢？\
我们用 ans2 和 ans5 表示边中 2 和 5 因子的总和。
同理，$ans5$ 表示为 $num5_{l}+num5_{r}-2\times num5_{lca(l,r)}$。\
最后再依次加上起点的因子数量并将 $ans2$ 和 $ans5$ 同其小数位数相加进行比较即可。记得一定要开 long long。~~(不开 long long 见祖宗)~~
### 代码
```
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=8e5+5;
int n,q;
int to[N],nxt[N],head[N],edge[N];
int a[N],f[N][25],lg[N],dep[N];
int num2[N],num5[N],xsd[N],d[N];
int cnt;
void add(int u,int v,int w,int x) {
cnt++;
to[cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
edge[cnt]=w;
xsd[cnt]=x;
}
int f2(int p) {
if(p==0)return 1e12;
int x=0;
while(p>0&&p%2==0) {
p/=2;
x++;
}
return x;
}
int f5(int p) {
if(p==0)return 1e12;
int x=0;
while(p>0&&p%5==0) {
p/=5;
x++;
}
return x;
}
void dfs(int now,int fa) {
dep[now]=dep[fa]+1;
f[now][0]=fa;
for(int i=1;(1<<i)<=dep[now];i++)
f[now][i]=f[f[now][i-1]][i-1];
for(int i=head[now]; i; i=nxt[i]) {
if(to[i]!=fa) {
d[to[i]]=d[now]+xsd[i];
num2[to[i]]=num2[now]+f2(edge[i]);
num5[to[i]]=num5[now]+f5(edge[i]);
dfs(to[i],now);
}
}
}
int lca(int x,int y) {
if(dep[x]<dep[y])swap(x,y);
while(dep[x]>dep[y]) {
int p=dep[x]-dep[y];
x=f[x][lg[p]];
}
if(x==y)return x;
for(int i=20; i>=0; i--) {
if(f[x][i]!=f[y][i]) {
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
signed main() {
cin>>n>>q;
for(int i=1; i<=n; i++)
cin>>a[i];
for(int i=1; i<n; i++) {
int u,v,x=0;
double w;
cin>>u>>v>>w;
while(w!=floor(w)) {
w*=10.0;
x++;
}
add(u,v,w,x);
add(v,u,w,x);
}
dfs(1,0);
for(int i=2; i<=n; i++)
lg[i]=lg[i/2]+1;
while(q--) {
int l,r;
cin>>l>>r;
int p=lca(l,r),dd=d[l]+d[r]-2*d[p];
int ans2=num2[l]+num2[r]-2*num2[p]+f2(a[l]);
int ans5=num5[l]+num5[r]-2*num5[p]+f5(a[l]);
//cout<<f2(a[l])<<' '<<f5(a[l])<<' '<<dd<<endl;
if(min(ans2,ans5)>=dd)cout<<"Yes";
else cout<<"No";
cout<<endl;
}
return 0;
}
```