题解：P4845 LJJ 爱数树

· · 题解

考虑 dp，设 f_{u,i,x} 表示以 u 为根的子树，有 i 个摄像头，最近的一个距离 u 为 x，如果 r 范围内都没有则视为 r+1 的最大代价，g_{u,i,x} 表示以 u 为根的子树，有 i 个摄像头，最远的一个距离没有覆盖的 w 距离为 x 的最大代价。

转移类似背包的转移。

若 x+y+1\le r，那么 g 这部分就全部覆盖了，因此 f_{u,i+j,x} \leftarrow f_{u,i,x}+g_{v,j,y}，否则 g_{u,i+j,y+1}\leftarrow f_{u,i,x}+g_{v,j,y}。

跟上面是类似的。

直接转移 f_{u,i+j,\min\{x,y+1\}}\leftarrow f_{u,i,x}+f_{v,j,y}。

直接转移 g_{u,i+j,\max\{x,y+1\}}\leftarrow g_{u,i,x}+g_{v,j,y}。

直接暴力做是 O(nkr^2) 的，前后缀优化一下可以做到 O(nkr)，注意到若 kr\ge n，显然整个树都可以覆盖，因此复杂度为 O(n^2)，可以通过。

具体的实现可以看代码，代码注释即为暴力转移。

#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
inline int read(){char c=getchar();int f=1,ans=0;while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();return ans*f;}
const int N=1e3+10,inf=1e18;
vector<vector<int>>f[N],g[N],pref[N],preg[N],suff[N],sufg[N];
vector<int>a[N];
int sz[N],n,k,r,w[N];
inline void chk(int &x,int y){x=(x>y?x:y);}
void dfs(int u,int fa){
    sz[u]=1;
    f[u].resize(2,vector<int>(r+2,-inf)),g[u].resize(2,vector<int>(r+2,-inf));
    f[u][0][r+1]=0,f[u][1][0]=w[u],g[u][0][0]=w[u];pref[u]=f[u],preg[u]=g[u],suff[u]=f[u],sufg[u]=g[u];
    for (int i=0;i<2;i++) for (int j=1;j<=r+1;j++) chk(pref[u][i][j],pref[u][i][j-1]);
    for (int i=0;i<2;i++) for (int j=1;j<=r;j++) chk(preg[u][i][j],preg[u][i][j-1]);
    for (int i=0;i<2;i++) for (int j=r;j>=0;j--) chk(suff[u][i][j],suff[u][i][j+1]);
    for (int i=0;i<2;i++) for (int j=r-1;j>=0;j--) chk(sufg[u][i][j],sufg[u][i][j+1]);
    for (auto v:a[u]) if (v^fa){
        dfs(v,u);
        vector<vector<int>>tmpf(min(sz[u]+sz[v],k)+1,vector<int>(r+2,-inf)),tmpg(min(sz[u]+sz[v],k)+1,vector<int>(r+2,-inf));
        for (int i=0;i<=min(sz[u],k);i++) for (int j=0;j<=min(sz[v],k);j++) if (i+j<=k){
        /*  // f+g
            for (int x=0;x<=r+1;x++) for (int y=0;y<=r;y++){
                if (x+y+1<=r) chk(tmpf[i+j][x],f[u][i][x]+g[v][j][y]);
                else chk(tmpg[i+j][y+1],f[u][i][x]+g[v][j][y]);
            } 
            // g+f
            for (int x=0;x<=r;x++) for (int y=0;y<=r+1;y++){
                if (x+y+1<=r) chk(tmpf[i+j][y+1],g[u][i][x]+f[v][j][y]);
                else chk(tmpg[i+j][x],g[u][i][x]+f[v][j][y]);
            }
            // f+f
            for (int x=0;x<=r+1;x++) for (int y=0;y<=r+1;y++)
                chk(tmpf[i+j][min(x,y+1)],f[u][i][x]+f[v][j][y]);
            // g+g
            for (int x=0;x<=r;x++) for (int y=0;y<=r;y++)
                chk(tmpg[i+j][max(x,y+1)],g[u][i][x]+g[v][j][y]); */
            for (int x=0;x<=r;x++){
                if (r-1-x>=0) chk(tmpf[i+j][x],f[u][i][x]+preg[v][j][r-1-x]);
                if (r-x<=r+1) chk(tmpg[i+j][x+1],suff[u][i][max(0ll,r-x)]+g[v][j][x]);
            }
            for (int x=0;x<=r;x++){
                if (r-x-1>=0) chk(tmpf[i+j][x+1],preg[u][i][r-x-1]+f[v][j][x]);
                if (r-x<=r) chk(tmpg[i+j][x],g[u][i][x]+suff[v][j][max(0ll,r-x)]);
            }
            for (int x=0;x<=r+1;x++){
                chk(tmpf[i+j][x],f[u][i][x]+suff[v][j][max(0ll,x-1)]);
                if (x+1<=r+1) chk(tmpf[i+j][x+1],suff[u][i][x+1]+f[v][j][x]);
            }
            for (int x=0;x<=r;x++){
                if (x-1>=0) chk(tmpg[i+j][x],g[u][i][x]+preg[v][j][x-1]);
                chk(tmpg[i+j][x+1],preg[u][i][min(r+1,x+1)]+g[v][j][x]);
            }
        }
        f[u]=pref[u]=suff[u]=tmpf,g[u]=preg[u]=sufg[u]=tmpg;
        for (int i=0;i<=min(sz[u]+sz[v],k);i++) for (int j=1;j<=r+1;j++) chk(pref[u][i][j],pref[u][i][j-1]);
        for (int i=0;i<=min(sz[u]+sz[v],k);i++) for (int j=1;j<=r;j++) chk(preg[u][i][j],preg[u][i][j-1]);
        for (int i=0;i<=min(sz[u]+sz[v],k);i++) for (int j=r;j>=0;j--) chk(suff[u][i][j],suff[u][i][j+1]);
        for (int i=0;i<=min(sz[u]+sz[v],k);i++) for (int j=r-1;j>=0;j--) chk(sufg[u][i][j],sufg[u][i][j+1]);
        sz[u]+=sz[v];
    }
}
inline void solve(){
    n=read(),k=read(),r=read();
    for (int i=1;i<=n;i++) a[i].clear(),w[i]=read(),f[i].clear(),g[i].clear(),pref[i].clear(),preg[i].clear();
    for (int i=1,u,v;i<n;i++) u=read(),v=read(),a[u].push_back(v),a[v].push_back(u); 
    if (k*r>=n){int ans=0;for (int i=1;i<=n;i++) ans+=w[i];return printf("%lld\n",ans),void();}
    dfs(1,0);
    int ans=0;for (int i=0;i<=min(sz[1],k);i++) for (int j=0;j<=r+1;j++) chk(ans,f[1][i][j]);
    printf("%lld\n",ans);
}
main(){
    int T=read();
    while(T--) solve(); 
    return 0;
}