lxl这就是你带出来的oier

Quintus09 · 2026-04-27 19:07:05 · 题解

哈哈哈，出题人学数据结构疯了被爆标了。诶，我怎么在卡常，原来我也疯了哈哈哈。

:::info[说句闲话（并非一句）] long__long 大神打了 rk14，先给他磕了。

3 月 31 号看完了《末日三问》，然后：

我的 at 等级分。

北斗八星。。。神秘凸包状物。我对于自己开 Ynoi 的决定产生深深的疑惑。

这场月赛也是我后由乃时代唯一拟人的一把了，即使 T2 写前缀和优化建图奇异搞笑半天，T3 数学太差奇异搞笑半天。

赛后看到 T4 标签激动不已，在 1\mathrm{h} 的思考后，我成功独立想出了 O(n\sqrt{n})！！！

这是我努力板刷 Ynoi 的成果！！！谁敢再说 Ynoi is useless！！！

搞什么，我会哭的。。。 :::

如果你疯了建议阅读这篇题解。

subtask0,1

遍历祖先动态规划即可。

subtask2

## subtask3,4,5 我认为 subtask3 就是被卡常的安慰分，subtask4 显然跟一棵树没什么本质区别，直接和一块了。考虑根号分治。 1. $a_i \le B

显然需要从 subtask2 的做法把线段树的 log 优化掉，也就是需要 O(\sqrt{n}) 查询，O(1) 修改的数据结构，显然是使用分块，而瓶颈在于修改后无法快速维护块内最大值。

对于修改位置的所在块，可以打 laz 标记，等查询时作为整块遍历到的时候暴力更新块内最大值。

每个点都会在 1 \sim B 对应的分块进行一次修改，这种特殊的修改方式可以感性理解出发现这样子是均摊 O(n \sqrt{n})。

a_i > B

dp_i = \max_{\substack{1 \le \operatorname{dep}_i - \operatorname{dep}_j \le \operatorname{len}}} \left( dp_j + a_j \bmod a_i \right)

可以转化成

dp_i = \max_{\substack{1 \le \operatorname{dep}_i - \operatorname{dep}_j \le \operatorname{len}}}\left( dp_j + a_j - \left\lfloor \frac{a_j}{a_i} \right\rfloor \cdot a_i\right)

而此时所有的 a_i 大于 B，所以 \left\lfloor \frac{a_j}{a_i} \right\rfloor 的取值 k 个数小于 \dfrac{V}{B}。

而对于每个 k 都对应这一个权值区间。

所以现在需要一个数据结构维护权值区间的最大值，满足 O(\sqrt{n}) 修改，O(1) 查询。

单点最大值用堆即可。

这可以使用 p7811 的做法，块内暴力维护前缀最大值和后缀最大值，两两整块之间的最大值用 st 表维护，而 st 表的单点修改为 O(\operatorname{num})（\operatorname{num} 为块的个数）。

因为此时通过根号分治，一定满足 a_i > B，所以若分块也使用这个 B 作为块长，一定满足每个询问的区间不是在单个块里面。查询时散块用暴力维护的前缀后缀最大值，整块用 st 表。

而对于修改逻辑就是个滑动窗口状物，显然你一定会有这个基础的。复杂度为 O(n \sqrt{n})。

根号分治两种情况的复杂度都十分的好，所以我们就用出题人和做题人同时学疯数据结构才会写的做法通过了该题。

上代码，代码需要一定卡常。


#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace IO {
    const int MAXBUF = 1 << 20;
    char buf[MAXBUF], *p1 = buf, *p2 = buf;
    char outbuf[MAXBUF], *outp = outbuf;
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXBUF, stdin), p1 == p2) ? EOF : *p1++)
    template<class T>
    inline void read(T &x) {
        x = 0; int f = 1; char ch = gc();
        while (!isdigit(ch)) { if (ch == '-') f = -1; ch = gc(); }
        while (isdigit(ch)) { x = x * 10 + (ch - '0'); ch = gc(); }
        x *= f;
    }
    template<class T>
    inline void write(T x) {
        if (x < 0) { *outp++ = '-'; x = -x; }
        static int sta[35]; int top = 0;
        do { sta[top++] = x % 10; x /= 10; } while (x);
        while (top) *outp++ = sta[--top] + '0';
    }
    inline void flush() {
        fwrite(outbuf, 1, outp - outbuf, stdout);
        outp = outbuf;
    }
}
using namespace IO;
const int N=3e5+5,B=200;
const ll inf=0x3f3f3f3f3f3f3f3f;
struct st{
    int to,nxt;
}edge[N<<1];
int head[N],cnt,a[N],dep[N],n,num,len,L[N/B+5],R[N/B+5],belong[N],tot[N],LG[N];
priority_queue < ll > q[N],del[N];
bool laz[B+5][N/B+5];
ll dp[N],ans,w[B+5][N],mx[B+5][N/B+5],st[N/B+5][15],pre[N],suf[N],b[N];
inline void add(int x,int y){
    edge[++cnt]={y,head[x]},head[x]=cnt;
}
inline void change(int p,int x,ll k){
    w[p][x]=k;
    laz[p][belong[x]]=1;
}
inline void solve(int p,int bel){
    mx[p][bel]=-inf;
    for (int i=L[bel];i<=R[bel];i++) mx[p][bel]=max(mx[p][bel],w[p][i]);
    laz[p][bel]=0;
}
inline ll gbc(int p,int x,int y){
    if (belong[x]==belong[y]){
        ll ret=-inf;
        for (int i=x;i<=y;i++) ret=max(ret,w[p][i]);
        return ret;
    }
    int bel_x=belong[x],bel_y=belong[y];ll ret=-inf;
    for (int i=x;i<=R[bel_x];i++) ret=max(ret,w[p][i]);
    for (int i=L[bel_y];i<=y;i++) ret=max(ret,w[p][i]);
    for (int i=bel_x+1;i<bel_y;i++){
        if (laz[p][i]) solve(p,i);
        ret=max(ret,mx[p][i]);
    }
    return ret;
}
inline ll get(int x){
    if (q[x].size()==del[x].size()) return -inf;
    while (del[x].size()&&q[x].top()==del[x].top()) q[x].pop(),del[x].pop();
    return q[x].top();
}
inline void ch(int x){
    ll val=get(x);
    int bel=belong[x];
    if (b[x]==val) return ;
    b[x]=val;
    pre[L[bel]]=b[L[bel]];
    suf[R[bel]]=b[R[bel]];
    for (int i=L[bel]+1;i<=R[bel];i++) pre[i]=max(pre[i-1],b[i]);
    for (int i=R[bel]-1;i>=L[bel];i--) suf[i]=max(suf[i+1],b[i]);
    ll mx=pre[R[bel]];st[bel][0]=mx;
    for (int k=1;k<=10;k++){
        for (int i=max(bel-(1<<k)+1,1);i<=min(bel,num-(1<<k)+1);i++) st[i][k]=max(st[i][k-1],st[i+(1<<(k-1))][k-1]);
    }
}
inline ll gbc_st(int x,int y){
    if (x>y) return -inf;
    int Lg=LG[y-x+1];
    return max(st[x][Lg],st[y-(1<<Lg)+1][Lg]);
}
inline ll gbc(int x,int y){
    if (belong[x]==belong[y]){
        ll ret=-inf;
        for (int i=x;i<=y;i++) ret=max(ret,b[i]);
        return ret;
    }
    ll ret=-inf;
    ret=max(max(ret,max(suf[x],pre[y])),gbc_st(belong[x]+1,belong[y]-1));
    return ret;
}
inline void dfs(int x,int fa){
    tot[dep[x]=dep[fa]+1]=x;
    if (x!=1){
        dp[x]=-inf;
        if (a[x]<=B) dp[x]=gbc(a[x],max(1,dep[x]-len),dep[x]-1);
        else{
            for (int k=0;k*a[x]<=3e5;k++){
                int LL=max(1,k*a[x]),RR=min((k+1)*a[x]-1,300000);
                dp[x]=max(dp[x],gbc(LL,RR)-k*a[x]);
            }
        }
        ans=max(ans,dp[x]);
    }
    for (int i=1;i<=B;i++) change(i,dep[x],dp[x]+a[x]%i);
    int fx=dep[x]-len<=0?0:tot[dep[x]-len];
    if (fx) del[a[fx]].push(dp[fx]+a[fx]),ch(a[fx]);
    q[a[x]].push(dp[x]+a[x]),ch(a[x]);
    for (int i=head[x];i;i=edge[i].nxt){
        int v=edge[i].to;
        if (v==fa) continue;
        dfs(v,x);
    }
    if (fx) q[a[fx]].push(dp[fx]+a[fx]),ch(a[fx]);
    del[a[x]].push(dp[x]+a[x]),ch(a[x]);
}
inline void build_block(){
    num=300000/B+(bool)(300000%B);
    for (int i=1;i<=num;i++){
        L[i]=(i-1)*B+1;
        R[i]=i*B;
    }
    R[num]=300000;
    for (int i=1;i<=num;i++){
        for (int j=L[i];j<=R[i];j++) belong[j]=i,b[j]=pre[j]=suf[j]=-inf;
        for (int j=0;j<=10;j++) st[i][j]=-inf;
    }
    for (int p=1;p<=B;p++){
        for (int i=1;i<=300000;i++) w[p][i]=-inf;
        for (int i=1;i<=num;i++) mx[p][i]=-inf;
    }
}
struct BL{
    int f[N];
    inline void dfs_baoli(int x,int fa){
        int v=fa;
        for (int i=1;i<=len;i++){
            if (!v) break;
            dp[x]=max(dp[x],dp[v]+a[v]%a[x]);
            v=f[v];
        }
        ans=max(ans,dp[x]);
        f[x]=fa;
        for (int i=head[x];i;i=edge[i].nxt){
            int v=edge[i].to;
            if (v==fa) continue;
            dfs_baoli(v,x);
        }
    }
}baoli;
signed main(){
    read(n); read(len);
    for (int i=2;i<=3e5;i++) LG[i]=LG[i>>1]+1;
    for (int i=1;i<=n;i++) read(a[i]);
    for (int i=1;i<n;i++){
        int x,y; read(x); read(y);
        add(x,y),add(y,x);
    }
    if (len<=2000){
        baoli.dfs_baoli(1,0);
        write(ans); *outp++ = '\n'; flush();
        return 0;
    }
    build_block();
    dfs(1,0);
    write(ans); *outp++ = '\n'; flush();
    return 0;
}