题解：CF2040E Control of Randomness

bsdsdb · 2024-12-10 15:00:11 · 题解

题意：一个人拿着 p(p\le 2000) 块钱在一棵树 (n\le 2000) 的节点 v 上走，规则如下：

• 如果这是第奇数步，向根走一步；
• 否则：
  • 付一块钱，向根走一步；
  • 或者，不付钱，向随机邻点走一步。

对 q 对 (v,p) 回答最优选择下，走到根的步数的最小期望值。

考虑 dp，设 \mathrm{dp}_{i,j,0/1} 表示目前走到节点 i，有 j 块钱，将要走第偶数 / 奇数步的答案。为了方便表述，定义 \mathrm{sc}_i:=\text{number of sons of }i,p_i:=\text{parent of }i. 初始情况显然是 \mathrm{dp}_{1,j,0/1}=1，奇数步也很好递推：\mathrm{dp}_{i,j,1}=\mathrm{dp}_{p_i,j,0}+1。对于偶数步，根据题目可得：

不付钱的情况与父亲和儿子都有关，比较难搞。但是不难注意到：\forall u\text{ is a son of }i:\mathrm{dp}_{u,j,1}=\mathrm{dp}_{p_u,j,0}+1=\mathrm{dp}_{i,j,0}+1，也就是说，对于不付钱的情况：

所以，\mathrm{dp}_{i,j,0}=\min\{\mathrm{dp}_{p_i,j-1,1},\mathrm{dp}_{p_i,j,1}+2\mathrm{sc}_i\}+1。

更进一步的逻辑细节请参考 this.

第一次见这种消掉 dp 的后效性用的是推式子而不是改状态的题。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
// tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>T;
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ldb;
//#define umap unordered_map
#define umap __gnu_pbds::cc_hash_table
#define mkp make_pair
#define prque priority_queue
#define emp emplace
#define empb emplace_back
#define empf emplace_front
random_device rndv;
mt19937 rd(rndv());
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ldb eps = 1e-8;
const vector<ll> millerrabin = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
inline void enter(){putchar('\n');}
inline void space(){putchar(' ');}
inline ll readll(){ll ret=0,k=1;char c;do{c=getchar();if(c=='-'){k=-1;}}while(('0'>c)|('9'<c));do{ret=(ret<<3)+(ret<<1)+c-48;c=getchar();}while(('0'<=c)&(c<='9'));return ret*k;}
inline void read(ll&x){x=readll();}
inline char readchar(){char ret;do{ret=getchar();}while(ret<=32);return ret;}
inline void read(char&x){x=readchar();}
inline string readstr(){string ret;char c;do{c=getchar();}while(c<=32);do{ret+=c;c=getchar();}while((c>32)&(c!=EOF));return ret;}
inline void read(string&x){x=readstr();}
inline void write(ll x){if(!x){putchar('0');return;}if(x<0){putchar('-');x*=-1;}char op[20]={};ll cur=0;while(x){op[++cur]=x%10+48;x/=10;}while(cur){putchar(op[cur--]);}}
inline ostream& operator<<(ostream& out, __int128 x){if(!x){out<<"0";return out;}if(x<0){out<<"-";x*=-1;}char op[40]={};ll cur=0;while(x){op[++cur]=x%10+48;x/=10;}while(cur){out<<op[cur--];}return out;}
// -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

const ll MAXN = 2e3 + 5;

ll n, q, coin, dp[MAXN][MAXN][2];
vector<ll> e[MAXN];

void srh(ll x, ll pr) {
    ll sc = e[x].size() - bool(pr);
    if (x == 1) {
        dp[x][coin][0] = dp[x][coin][1] = 0;
    } else {
        dp[x][coin][1] = dp[pr][coin][0] + 1;
        if (coin > 0) {
            dp[x][coin][0] = min(dp[pr][coin - 1][1], dp[pr][coin][1] + (sc << 1)) + 1;
        } else {
            dp[x][coin][0] = dp[pr][coin][1] + (sc << 1) + 1;
        }
    }
    for (ll i : e[x]) {
        if (i == pr) {
            continue;
        }
        srh(i, x);
    }
}

void init() {
    for (ll i = 1; i <= n; ++i) {
        e[i].clear();
        for (ll j = 0; j <= n; ++j) {
            dp[i][j][0] = dp[i][j][1] = 0;
        }
    }
    coin = 0;
}
int mian() {
    read(n), read(q);
    for (ll i = 1; i < n; ++i) {
        ll u, v;
        read(u), read(v);
        e[u].empb(v), e[v].empb(u);
    }
    for (coin = 0; coin <= n; ++coin) {
        srh(1, 0);
    }
    while (q--) {
        ll x, p;
        read(x), read(p);
        write(dp[x][p][1]), enter();
    }
    return 0;
}

int main() {
    ll T;
    read(T);
    while (T--) {
        init();
        mian();
    }
    return 0;
}

;             ;;;;;;;;          ;
;                   ;          ; ;
;                  ;          ;   ;
;                 ;          ;     ;
;                ;          ;;;;;;;;;
;               ;          ;         ;
;              ;          ;           ;
;;;;;;;;;;;   ;;;;;;;;   ;             ;

   ;                        ;
  ;                          ;
 ;                            ;
;                              ;
;                              ;
;                              ;
 ;                            ;
  ;         ;;          ;;   ;
   ;        ;;          ;;  ;