Wuyanru's blog
0%

[LGR-129] 宿命 | Regulation of Destiny

发表于 分类于 ，

非常好剪枝，使我的 dp 转移旋转。

题目链接

题意

给定一棵 个点的树与一个数字 。

对于每一个点，现有两种防护措施，代价分别为 ，每一个点可以选择至多一种防护措施。

若选择了第一种防护措施，这个点与其所有相邻点将会被保护。

若选择了第二种防护措施，这个点和与他距离恰好为 的所有点将会被保护。

现在要求所有点都被保护，求最小总代价。

。。

题解

首先比较容易能看出来，这题正解应该是一个树形 dp。

设 表示 这棵子树，当前可以向外保护 这些距离，自己内部距离自己 这些距离的点还没有被保护，最小代价是多少。其中 均为 位的二进制数，特殊的， 范围是二进制从低到高第 位。

考虑合并两个子树， 和子树 会合并到 。这里 表示集合内所有数字 ，相当于二进制数的左移右移操作。

这样做显然是对的，时间复杂度是 ，过集贸。

考虑画一个转移的图出来。

又能想到一个问题，对于一个状态，若将其 的某个 变为 ，新得到的状态显然代价是更小的。同理， 里的一个 变成 ，代价显然更小。

扣掉不优的状态，就只剩下这么一点了。

所以一次合并，其实只需要做 级别数量的转移，事先搜出所有的转移存下来即可。

时间复杂度 。

代码

卡着过的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
ll dp[205][16384];
ll fp[16384];
vc<int>G[205];
vc<pi>g[16384];
int v1[205];
int v2[205];
vc<pi>o[4];
int n,r,c;
inline void init()
{
    o[0].push_back(pi(0,0));
    o[1].push_back(pi(1,1));
    o[1].push_back(pi(2,2));
    o[1].push_back(pi(3,3));
    o[2].push_back(pi(1,2));
    o[3].push_back(pi(1,3));
    o[3].push_back(pi(3,2));
}
void dfs(int num,int sta1,int sta2,int sta3,int sta4,int sta5,int sta6)
{
    if(num>r)
    {
        if(sta1&1) return ;
        if(sta2&(1<<r)) return ;
        if(sta4&1) sta4-=1;
        if(sta3&(1<<r)) sta3^=1<<r;
        sta3<<=1,sta4>>=1;
        if(sta5&1) sta5-=1;
        if(sta6&(1<<r)) return ;
        int v1=(sta1<<(r-1))|sta2;
        int v2=(sta3<<(r-1))|sta4;
        int v3=(sta5<<(r-1))|sta6;
        g[v1].push_back(pi(v2,v3));
        c++;
        return ;
    }
    for(int i=0;i<4;i++) for(auto P:o[i])
    {
        int j=P.first,k=P.second;
        dfs(num+1,(sta1<<1)|((i&2)>>1),(sta2<<1)|(i&1),(sta3<<1)|((j&2)>>1),(sta4<<1)|(j&1),(sta5<<1)|((k&2)>>1),(sta6<<1)|(k&1));
    }
}
inline void Min(ll &a,ll b)
{
    if(b<a) a=b;
}
inline void push(int num,int sta1,int sta2,int y)
{
    Min(dp[num][(sta1<<(r-1))|sta2],y);
}
inline void run(int num)
{
    for(int i=0;i<r;i++) for(int j=0;j<(1<<(2*r));j++) if(j&(1<<(r+i)))
        Min(dp[num][j^(1<<(r+i))],dp[num][j]);
    for(int i=0;i<r;i++) for(int j=0;j<(1<<(2*r));j++) if(j&(1<<i))
        Min(dp[num][j],dp[num][j^(1<<i)]);
}
void dfs(int num,int fa)
{
    push(num,0,1,0);
    push(num,1<<1,0,v1[num]);
    push(num,1<<r,0,v2[num]);
    run(num);

    for(int p:G[num]) if(p!=fa)
    {
        dfs(p,num);
        memcpy(fp,dp[num],sizeof(fp));
        memset(dp[num],0x3f,sizeof(dp[num]));
        for(int i=0;i<(1<<(2*r));i++) for(auto P:g[i])
        {
            int j=P.first,k=P.second;
            Min(dp[num][k],fp[i]+dp[p][j]);
        }
        run(num);
    }
}
int main()
{
    n=read(),r=read();init();
    dfs(0,0,0,0,0,0,0);
    // cout<<c<<endl;

    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=n;i++) v1[i]=read(),v2[i]=read();
    memset(dp,0x3f,sizeof(dp));
    dfs(1,1);

    ll ans=inf;
    for(int i=0;i<(1<<r);i++) ans=min(ans,dp[1][i<<r]);
    printf("%lld\n",ans);
    return 0;
}