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

· · 题解

std 居然是根号的吗，/jy。

约定：我们把去掉 v_0 =1 限制后的所有合法序列称为“树上子序列”，v_0 称为该树上子序列的顶。

我们先考虑一个 dp，设 dp_i 为以 i 点为顶的任意树上子序列的最大价值。那么 i 点就会选择拼在子树内某个树上子序列的前面，有转移

dp_i = \max_{j \in subtree_i \land dep_j - dep_i \le L} dp_j + a_i \bmod a_j

答案就是 dp_1。这是一个 O(n^2) 的 dp。

考虑一下优化，感觉有些时候，在当前转移的点 i 和枚举的点 j 之间再插入一个数会更优，这个时候就不需要枚举 j。也就是说类似于有 x \bmod y + y \bmod z \ge x \bmod z 这种东西。

手模一下，如果 2y > x，那么 x \bmod y + y \bmod z \ge x \bmod z 好像一定会成立。考虑分讨证明：

那么 x \bmod y = x。而 x \bmod z \le x，所以 x \bmod y + y \bmod z \ge x \bmod z。

那么 x \bmod y = x - y。而又有 x - y \ge x \bmod z - y\bmod z（这个较容易证），等量代换再移项就可得到 x \bmod y + y \bmod z \ge x \bmod z。

好现在我们有了这个剪枝优化：对于每个点 i，以 dfs 的方式在子树中尝试转移。如果到某个点 j 使得 2a_j > a_i，就不再往下。

加上去，你会发现，过了？？？这是怎么回事呢。

让我们分析一下复杂度。对于每个点，它作为被转移点时，设向上依次有 j,k 枚举了它。那么肯定有 2a_j \le a_k，否则转移 k 时 dfs 到 j 就会返回，不会到 i。那么对于每个点，至多有 O(\log V) 个点在转移时枚举到它。所以这样的时间复杂度是 O(n \log V) 的。

代码很短。

#include<bits/stdc++.h>
#define i128 __int128
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define Pii pair<int,int>
#define fi first
#define se second
#define inline
#define f(x,y) fixed<<setprecision(y)<<x
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,rp,stdin),p1==p2)?EOF:*p1++)

using namespace std;
const int N=3e5+10;
const int rp=1e6+10;

int n,m,dep[N],p[N]; ll dp[N];//ll
vector<int> vt[N];
char buf[rp],*p1=buf,*p2=buf;

inline int read()
{
    int x=0,f=1; char c=0;
    while(!isdigit(c)) {if(c=='-') f=-1; c=gc();}
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=gc();
    return x*f;
}

inline char read_ch()
{
    char c=0;
    while((!isalpha(c))&&(!isdigit(c))) c=gc();
    return c;
}

inline void dfs2(int x,int f,int rt)
{
    if(dep[x]-dep[rt]>m) return;//距离不满足条件了
    dp[rt]=max(dp[rt],dp[x]+p[rt]%p[x]);//把当前点转移上去
    if(p[x]+p[x]>p[rt]) return;//剪枝保证复杂度
    for(auto a:vt[x]) if(a!=f) dfs2(a,x,rt);//往下
}

inline void dfs(int x,int f)
{
    dep[x]=dep[f]+1;
    for(auto a:vt[x]) if(a!=f) dfs(a,x),dfs2(a,x,x);//先 dfs 再去转移 x
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m; int u,v;
    for(int i=1;i<=n;++i) cin>>p[i];
    for(int i=1;i<n;++i)
    {
        cin>>u>>v;
        vt[u].push_back(v);
        vt[v].push_back(u);
    }
    dfs(1,0); cout<<dp[1];//答案就是以 1 为顶的树上子序列
    return 0;
}
/*
ぼくはどこにいるの
ここはどこにあるの
いつから夢の中
彷徨い歩いてる
*/