题解：P16356 「Diligent-OI R3 D」神秘树

Cadmus · 2026-04-27 11:47:03 · 题解

一句话剪枝，暴力变 AC！暴踩 std，一秒水紫题！！

在暴力 DP 基础上加一句话剪枝复杂度就可以变成 O(n\log V)！！

暴力 DP 是设 f_u 表示 u 作为 v_0 的最大答案，转移的时候枚举子树内的点 v 作为 v_1。

加上这么一个判断：如果 2a_v>a_u，转移后直接返回，不继续递归子树。

先放代码：

#include <bits/stdc++.h>
using namespace std;
#define N 300005
int n,L,u,v,a[N],d[N];
long long f[N];
vector<int> g[N];
void zhuanyi(int u,int fa,int x){
    if(d[u]>d[x]+L)return;
    f[x]=max(f[x],f[u]+a[x]%a[u]);
    if(a[u]*2>a[x])return; //一句话剪枝，暴力变AC！！
    for(int v:g[u])
        if(v!=fa)zhuanyi(v,u,x);
}
void dfs(int u,int fa){
    for(int v:g[u])
        if(v!=fa)d[v]=d[u]+1,dfs(v,u),zhuanyi(v,u,u);
}
int main(){
    cin>>n>>L;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++)cin>>u>>v,g[u].push_back(v),g[v].push_back(u);
    dfs(1,0);
    cout<<f[1]<<endl;
}

为什么这样剪枝是对的？因为如果 2y>x，那么 (x\bmod z)\le(x\bmod y)+(y\bmod z)，如果 u 子树里面再转移，不如在前面加一个 u 进去！！

为什么复杂度就是 O(n\log V)？因为对于一个 u，设两个访问到它的 x 是 x_1,x_2（x_1<x_2），那么一定 2x_1\le x_2，否则访问到 x_1 就返回了！！所以对于一个 u，访问到它的 zhuanyi 次数是 \mathcal O(\log V) 的，总复杂度就是 O(n\log V)！！