“蔚来杯“2022牛客暑期多校训练营10 K.You are given a tree...

原题链接

传送

题目大意

给定包含 $n$ 个节点的树 $T=(V,E)$， 节点 $i$ 具有权值 $a_i$，每条边有一定边权值。
求子集 $S\subseteq V$，满足最多有 $k$ 个点具有不同的权值，且最大化“生成边”的权值和，边 $e$ 是生成边，当且仅当存在 $u,v\in S$，边 $e$ 在 $u,v$ 的简单路径上。
输出最大的“生成边”的权值和。

题解

考虑点权范围 $1\le a_i\le k$，
我们考虑用状压DP枚举每一位的状态，在树上更新答案。
设 $d{p}_{x,v}$ 表示在 $x$ 的子树下，状态为 $v$ 内的点权所能组成的最大边权值和。
可以发现， 将子情况汇总，
加入链接顶点的边所能构成的更新可以分成两部分：
该边的连接的子节点和其他的部分，由于点权不冲突，
所以转移式显然为为：
$$d{p}_{x,v}=max(d{p}_{x,v},d{p}_{son,s}+d{p}_{x,v-s}+w)(s\in v)$$
枚举即可，复杂度为 $O(n\ast 3^k)$。
考虑回点权初始范围，最终选取的点权数肯定在$1\le a_i\le k$ 内，
随机分配一个其中的权值给 $a_i$，
如果随机分配后找到一组解，那它在分配前肯定也是一组符合的情况，
而原问题的最优解在某种特殊情况下，即其中的颜色刚好分配不同，肯定能给出结果，之前的状压也肯定能找出该结果。
选取随机数使得最优解中各不相同的概率为 $k!k^k$ ，大约为 $\frac{1}{26}$，在选取一个合适的数据组数(大约为200左右)进行计算验证后，即可得出最优解。
复杂度为 $O(T\ast n\ast 3^k)$。

参考代码

#include
#define ll long long
using namespace std;
const int N=5e3+5;
const ll inf=1e18+7;         //-1e9~1e9
ll dp[N][1<<5],ans;
vector<pair<int,int> > v1[N],v[N];
int f[N],w[N];
int n,k,T,m;
void dfs(int x,int fa)        //状压DP
{
    for(int i=1;i<=m;i++)
        dp[x][i]=-inf;
    dp[x][0]=0;
    int now=1<<w[f[x]];
    for(int i=0;i<v[x].size();i++)           //从子树转移
    {
        pair<int,int> son=v[x][i];
        if(son.first==fa)
            continue;
        dfs(son.first,x);
        for(int p=m;p>=0;p--)
            for(int j=p;j;j=(j-1)&p)       //枚举状态
            {
                ll tp=dp[son.first][j]+dp[x][p^j]+son.second;
                dp[x][p]=max(dp[x][p],tp);
                if(j!=p || (j&now)==0)
                    ans=max(ans,tp);     //比较最优解
            }
    }
    dp[x][now]=max(dp[x][now],0ll);
}
int main()
{
    scanf("%d%d",&n,&k);
    m=(1<<k)-1;
    for(int i=1;i<=n;i++)
        scanf("%d",&f[i]);
    for(int i=2;i<=n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }
    T=200;
    while(T--)
    {
        for(int i=1;i<=n;i++)       //随机
            w[i]=rand()%k;
        dfs(1,0);
    }
    printf("%lld\n",ans);
}
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