题解：P8972 『GROI-R1』 一切都已过去

P8972 『GROI-R1』 一切都已过去 题解

分析

从数据范围很容易发现，如果我们把边权累乘再判整数，炸掉是必然的，这时候，我们来发现一个性质：只有小数部分有 2 和 5 相乘的时候，才可能变成整数。当然，这并不是绝对的，例如 2.02 \times 5 就不是整数。从上面举的例子很容易发现一个性质：两个实数的乘积是否为整数与小数点数位也有关系。一对 2 和 5 可以抵消掉一个小数点数位（2 和 5 可以在任意且不同数位上，并且 2 和 5 的倍数也有用）。这时，我们可以将边权通过不断 \times 10 变成整数，并分解质因数分别求因数中 2 和 5 的个数（点权也要处理）。2 和 5 的个数求出来了，小数点数位也很好处理。最终的小数点位数应该是所有路径上的边权小数点位数之和，所以我们在将边权化整数时再维护一个变量统计小数点位数并记录到邻接矩阵里。若路径 x 到 y 的总边权乘上 x 的点权得到的结果中 2 的个数和 5 的个数大于或等于总小数点位数，则其为整数。分别维护即可。

注意：若边权或点权为 0 则对应维护的当前点权或点权的 2 和 5 赋予极大值。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
const int inf=1e16;
struct node
{
    int y, w, dlp;//dlp表示小数点位数，Decimal Places
};
int n, m, s, dep[N], dp[N][21], dis[N], cnt2[N], cnt5[N], a[N];
vector<node> nbr[N];
int count_two(int x)
{
    if(x==0)
    {
        return inf;
    }
    int cnt=0;
    while(x!=0&&x%2==0)
    {
        cnt++;
        x/=2;
    }
    return cnt;
}
int count_five(int x)
{
    if(x==0)
    {
        return inf;
    }
    int cnt=0;
    while(x!=0&&x%5==0)
    {
        cnt++;
        x/=5;
    }
    return cnt;
}
void pre_lca(int cur, int fa)
{
    dp[cur][0]=fa;
    dep[cur]=dep[fa]+1;
    for(int i=1;(1<<i)<=dep[cur];i++)
    {
        dp[cur][i]=dp[dp[cur][i-1]][i-1];
    }
    for(auto i:nbr[cur])
    {
        int nxt=i.y;
        if(nxt!=fa)
        {
            dis[nxt]=dis[cur]+i.dlp,cnt2[nxt]=cnt2[cur]+count_two(i.w),cnt5[nxt]=cnt5[cur]+count_five(i.w);
            pre_lca(nxt,cur);
        }
    }
}
int lca(int x, int y)
{
    if(dep[x]>dep[y])
    {
        swap(x,y);
    }
    for(int i=20;i>=0;i--)
    {
        if(dep[x]<=dep[dp[y][i]])
        {
            y=dp[y][i];
        }
    }
    if(x==y)
    {
        return x;
    }
    for(int i=20;i>=0;i--)
    {
        if(dp[x][i]!=dp[y][i])
        {
            x=dp[x][i];
            y=dp[y][i];
        }
    }
    return dp[x][0];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<n;i++)
    {
        int x, y;
        double v;
        cin>>x>>y>>v;
        int dlp=0;
        while(v!=floor(v))
        {
            v*=10.0;
            dlp++;
        }
        nbr[x].push_back((node){y,floor(v),dlp});
        nbr[y].push_back((node){x,floor(v),dlp});
    }
    pre_lca(1,0);
    for(;m;m--)
    {
        int x, y;
        cin>>x>>y;
        int tmp=lca(x,y);
        if(min(cnt2[x]+cnt2[y]-2*cnt2[tmp]+count_two(a[x]),cnt5[x]+cnt5[y]-2*cnt5[tmp]+count_five(a[x]))>=dis[x]+dis[y]-2*dis[tmp])
        {
            cout<<"Yes\n";
        }
        else
        {
            cout<<"No\n";
        }
    }
}