更差的阅读体验
注意到，对于式子 \(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;
}