题解：P14013 [POCamp 2023] 送钱 / The Generous Traveler

· · 题解

更好的阅读体验

注意到，对于式子 a \bmod b，如果 a > b 则 a 的值不变；如果 a \le b 则 a 的值至少折半。

这意味着，我们对数字 X 多次取模，实际上只有 O(\log X) 次取模真正修改了它的值。所以我们可以暴力找到每一个真正修改它值得点，进行取模操作。

于是问题就转化为，在树链上找到最近的 \le X 的节点。

这个问题十分简单。我们先树剖，然后在 dfs 序上做一个 RMQ，查询的时候直接二分即可。

那么这道题就做完了，复杂度 O(n \log n \log V)，其中 V 是值域。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 200006
#define fi first
#define se second
using namespace std;
using pii=pair<int,int>;
int n,q,a[N];
int sz[N],son[N],fa[N],tp[N],dep[N],dfn[N],id[N],dfs_clock;
vector<int> G[N];
struct ST_table {
    int st[N][20],lg[N];
    void build()
    {
        for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
        for(int i=1;i<=n;i++)st[i][0]=a[id[i]];
        for(int j=1;(1<<j)<=n;j++)
            for(int i=1;i+(1<<j)-1<=n;i++)
                st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
    }
    int query(int l,int r)
    {
        int k=lg[r-l+1];
        return min(st[l][k],st[r-(1<<k)+1][k]);
    }
}ST;
void dfs1(int u,int f)
{
    dep[u]=dep[fa[u]=f]+1,sz[u]=1;
    for(int v:G[u])if(v!=f)
    {
        dfs1(v,u),sz[u]+=sz[v];
        if(sz[v]>sz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int t)
{
    id[dfn[u]=++dfs_clock]=u,tp[u]=t;
    if(son[u])dfs2(son[u],t);
    for(int v:G[u])
        if(v!=fa[u]&&v!=son[u])dfs2(v,v);
}
void solve_up(int &x,int l,int r)
{
    if(l>r)swap(l,r);
    for(int i=l;i<=r;)
    {
        int lb=i,rb=r,res=r+1;
        while(lb<=rb)
        {
            int mid=lb+rb>>1;
            if(ST.query(i,mid)<=x)rb=mid-1,res=mid;
            else lb=mid+1;
        }
        if(res<=r)x%=a[id[res]];
        i=res+1;
    }
}
void solve_down(int &x,int l,int r)
{
    if(l>r)swap(l,r);
    for(int i=r;i>=l;)
    {
        int lb=l,rb=i,res=l-1;
        while(lb<=rb)
        {
            int mid=lb+rb>>1;
            if(ST.query(mid,i)<=x)lb=mid+1,res=mid;
            else rb=mid-1;
        }
        if(res>=l)x%=a[id[res]];
        i=res-1;
    }
}
int getLCA(int u,int v)
{
    while(tp[u]!=tp[v])
    {
        if(dep[tp[u]]<dep[tp[v]])swap(u,v);
        u=fa[tp[u]];
    }
    return dep[u]<dep[v]?u:v;
}
vector<pii> get(int u,int anc)
{
    vector<pii> ret;
    while(tp[u]!=tp[anc])
        ret.push_back({dfn[tp[u]],dfn[u]}),u=fa[tp[u]];
    ret.push_back({dfn[anc],dfn[u]});
    return ret;
}
main()
{
    scanf("%lld%lld",&n,&q);
    for(int i=1,u,v;i<n;i++)
        scanf("%lld%lld",&u,&v),G[u].push_back(v),G[v].push_back(u);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    dfs1(1,0),dfs2(1,1),ST.build();
    while(q--)
    {
        int u,v,x,LCA;
        scanf("%lld%lld%lld",&u,&v,&x),LCA=getLCA(u,v);
        vector<pii> vec1=get(u,LCA),vec2=get(v,LCA);
        reverse(vec2.begin(),vec2.end());
        for(auto i:vec1)solve_down(x,i.fi,i.se);
        for(auto i:vec2)solve_up(x,i.fi,i.se);
        printf("%lld\n",x);
    }
    return 0;
}