P8970 树上邻跃数点 题解

· · 题解

这道题的两种覆盖分别是覆盖相【邻】的点和覆盖【跃】过一定距离的点，所以我愿称它为“树上 \mathsf{linyue} 数点”（

首先这个数据范围肯定是状压 dp，我们可以设计出一个很显然的状态：dp_{i,j,s1,s2}，其中 j 为 0 或 1，表示这个点本身是否被覆盖；s1,s2 是两个长为 r 的 01 串，第 k 位表示第 i 个点向下和向上距离为 k 的点是否被覆盖好了，而 dp 数组就存储在这个状态下的花费最小值。

想要实现从儿子到父亲的转移是容易的，但是合并两个兄弟就很难办。将 dp_{i1,j1,s11,s12} 和 dp_{i2,j2,s21,s22} 合并的状态是：

dp_{fa,j1 \lor j2,(s11 \lor s22)\land(s12 \lor s21),s12 \lor s22}

直接转移需要枚举两边的所有状态，复杂度 O(n2^{4r})，显然过不去……

进一步发掘转移性质，由于 s1,s2 的转移只涉及位运算，我们将它们每位分开考虑，我们将 s11、s12、s21、s22 合并后的 s1、s2 的同一位之间的对应关系列成表：

* 00 01 10 11
00 00 01 00 11
01 01 11 01 11
10 00 01 10 11
11 11 11 11 11

横轴是将 s11、s12 的某一位连着写到一起，纵轴是将 s21、s22 的这一位连着写到一起，中间就是将合并后的 s1、s2 的这一位连着写到一起。

进一步阅读题面，发现这不是一道计数题，而是一道最优化题，也就是说，我们可以让“0”表示 “任意状态” 而非 “未被覆盖”，最后的答案不会有变化！这样的话，我们转移时，可以先枚举合并后的结果，然后不需要让两个孩子的状态恰好合并为此结果，只要保证它们合并之后不会比目标多出某个位置上的 1 就可以。这样可以大大优化复杂度！

若目标状态的 s1、s2 的某一位连起来写是下面的可能，那么只需要考虑 s11、s12、s21、s22 的这一位连起来写的结果在下列的状态即可。

这样的转移一共有 r 位，每位只需要枚举上面的 7 种情况，因此复杂度是是O(n7^r)，经过亿些卡常就可以通过此题了！

所以这题其实好像没有只会 O(n8^r) 不会正解的可能啊，所以也没必要卡常卡这么夸张吧（

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#define int long long
#define set(x,y,z) x[(i)]|=(y<<(r-1-j)),x[(i)]|=(z<<(r+1+j))
#define upd(a,b) a=min((a),(b));
using namespace std;
int n,r,mv,a[205],b[205],dp[205][65534],cl[999999],cr[999999],cm[999999];
vector<int> l[205];
void dfs(int now,int fa){
    for(int i=0;i<(1<<r);i++)dp[now][i]=0;
    int fis=0;
    for(int ii=0;ii<=l[now].size();ii++){
        int i=l[now][ii];
        if(i==fa)continue;
        dfs(i,now);
        if(fis==0){
            fis=1;
            for(int j=0;j<(1<<(r*2+1));j++){
                dp[now][j]=dp[i][j];
            }
            continue;
        }
        int pas[65535];
        for(int j=0;j<(1<<(r*2+1));j++){
            pas[j]=dp[now][j];dp[now][j]=0x0101010101010101ll;
        }
        for(int j=0,*pm=cm,*pl=cl,*pr=cr;j<mv;j++,pm++,pl++,pr++){
            upd(dp[now][*pm],pas[*pl]+dp[i][*pr]);
            upd(dp[now][(*pm)|(1<<r)],min(pas[(*pl)|(1<<r)]+dp[i][*pr],pas[*pl]+dp[i][(*pr)|(1<<r)]));
        }
    }
    int ca=(1<<(r))|(1<<(r-1))|(1<<(r+1)),cb=(1)|(1<<(r))|(1<<(r*2));
    int pas[65535];
    for(int j=0;j<(1<<(r*2+1));j++){
        pas[j]=dp[now][j];dp[now][j]=0x0101010101010101ll;
    }
    for(int i=0;i<(1<<(r*2+1));i++){
        upd(dp[now][i|ca],pas[i]+a[now]);
        upd(dp[now][i|cb],pas[i]+b[now]);
        upd(dp[now][i],pas[i]);
    }
    for(int j=0;j<(1<<(r*2+1));j++){
        pas[j]=dp[now][j];dp[now][j]=0x0101010101010101ll;
    }
    for(int i=0;i<(1<<(r*2+1));i++){
        if(i&1){
            dp[now][i>>1ll]=pas[i];
        }
    }
    for(int j=0;j<=r*2;j++){
        for(int h=0;h<(1<<(r*2));h++){
            upd(dp[now][h],dp[now][h|(1<<j)]);
        }
    }
}
signed main(){
    memset(dp,1,sizeof(dp));
    scanf("%lld%lld",&n,&r);
    for(int i=1;i<n;i++){
        int in1,in2;
        scanf("%lld%lld",&in1,&in2);
        l[in1].push_back(in2);l[in2].push_back(in1);
    }
    for(int i=1;i<=n;i++)scanf("%lld %lld",a+i,b+i);
    mv=1;for(int i=1;i<=r;i++)mv*=7;
    for(int i=0;i<mv;i++){
        for(int j=0,nv=i;j<r;j++,nv/=7){
            switch(nv%7){
                case 0:{set(cl,0,0);set(cr,0,0);set(cm,0,0);break;}
                case 1:{set(cl,0,0);set(cr,0,1);set(cm,0,1);break;}
                case 2:{set(cl,0,1);set(cr,0,0);set(cm,0,1);break;}
                case 3:{set(cl,1,0);set(cr,1,0);set(cm,1,0);break;}
                case 4:{set(cl,0,0);set(cr,1,1);set(cm,1,1);break;}
                case 5:{set(cl,1,1);set(cr,0,0);set(cm,1,1);break;}
                case 6:{set(cl,0,1);set(cr,0,1);set(cm,1,1);break;}
            }
        }
    }
    dfs(1,0);
    printf("%lld\n",dp[1][(1<<r)-1]);
}

题外话：

“泥泞”、“执念”，很容易让我联想到“迷乱的心灵之泽，执念的重生之翼”；看完《流浪地球2》后，我也发觉所谓“执念”真的很能触动我，从很久之前开始；再加上如本题解开头的神秘谐音梗，所以这题还是对我很有特殊的意义的。

结果不知道咋的，明明没什么难点的题我却一直卡住，没有什么思路，导致“做出此题”都快成我的执念了（

现在我已经退役 4 个月了，突然想起来“树上 \mathsf{linyue} 数点”这个梗，然后一推直接就推完了——深深地感觉到自己曾经有多小丑。不过，这也算是加深了这题对我的重要程度（

“我相信，所谓的力量，其实，就是心中的执念。”