题解：CF486D Valid Sets

· · 题解

前言

学校模拟赛打的，场后发现好简单自己怎么没想到。

为 CSP rp++，特作此篇。

题意简述

有一棵树，你可以选取若干个节点，使得任意两个节点直接的简单路径上的所有节点都被选取，且这些节点的权值极差 \leq d。

思路

对于 n \leq 2 \times 10^3 考虑每次枚举然后跑树形 dp，这样的时间复杂度是 O(n^2) 的。

考虑将权值从大到小排序后，钦定集合中的最大值。最大值的种类数量显然是 n 个节点的权值，于是我们枚举每个节点的权值作为最大值，并将该节点作为根跑树形 dp。

在 dp 时，可行的儿子节点 v 需要满足在排序后的位置在根节点之后（这个显然可以直接用标记处理），且 w_{root}-w_v>d。根据乘法原理，状态转移方程是：

dp_u=\Pi_v (dp_v+1)

初始化就是将所有节点 x 的 dp_x 设置为 1。最后计算出每次 dp 后的 dp_{root} 之和取模即可。

Code

:::success[AC Code]

#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int MOD = 1e9 + 7;
const int N = 2e3 + 5;
int d,dp[N],w[N],rt;
struct node{
    int id,x;
    bool operator < (const node &ot) const{
        return x > ot.x;
    }
}a[N];
bool vis[N];
vector<int> ve[N];
void dfs(int now,int root){
    dp[now] = 1;
    for(auto v : ve[now]){
        if(v == root || vis[v] || w[rt] - w[v] > d) continue;
        dfs(v,now);
        dp[now] = dp[now] * (dp[v] + 1) % MOD;
    }
}
void solve(){
    int n; cin >> d >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i].x;
        a[i].id = i;
        w[i] = a[i].x;
    }
    sort(a + 1,a + n + 1);
    for(int i = 1;i < n;i++){
        int u,v; cin >> u >> v;
        ve[u].pb(v);
        ve[v].pb(u);
    }
    int ans = 0;
    for(int i = 1;i <= n;i++){
        vis[a[i].id] = 1;
        rt = a[i].id;
        for(int j = 1;j <= n;j++) dp[j] = 0;
        dfs(a[i].id,0);
        (ans += dp[a[i].id]) %= MOD;
    }
    cout << ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int tid,T = 1;
    while(T--) solve();
    return 0;
}

:::

启发

场上的思路是枚举集合的 LCA，不难发现可以选取的节点其实是接在这个 LCA 上的若干子树。但这样可能要用换根 dp，还是有一些困难，于是我毙了这个想法。同机房有人用这种思路过了这个题，欢迎读者思考交流。