AT_aising2019_e

· · 题解

题意是给定一棵树，要求断开一些边，使得连通块要么是全正数，要么是总和为负数。

数据范围 n \le 5000，暗示有 O(n^2) 的做法，树上的话一般都是考虑树形 DP。

挺简单的一个想法是把权值和答案互换，状态设为 f_{i,j} 表示以 i 为根，然后断开了 j 次。

我们思考如何加入一个子树，会发现这东西好像不太好转移呢，由于题目中连通块和全正有关，不妨设 f_{i,j,0/1} 表示以 i 为根，然后断开了 j 次之后是否全正。

然后考虑 f_{i,j,1} 如何转移，发现加入一个子树 f_{v,k,1} 就会变成 f_{i,j+k,1}，我们不能加入一个子树 f_{v,k,0}，因为这样会导致这个状态变成 f_{i,j+k,0}。

然后考虑 f_{i,j,0} 如何转移，这东西就比较宽松了，f_{v,k,0/1} 都可以转移到这里。

以上是比较简单的树形 DP，然后我们考虑断开一个子树，发现需要断开一个子树，必须满足总和小于 0 或者它是全是正数，两种情况稍微判断一下就可以了。

对于 dp 数组初值设为正无穷，同时转移的时候用另外一个辅助数组来做会比较方便。

感谢 @Loser_king 学长帮助。

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int INF=5e3+5;
struct _node_edge{
    int to_,next_;
}edge[INF<<1];
// f[x][y][0/1] 表示 x 为根的子树内，断开了 y 次，当前是否是全正  1/0 的总和最小值 
int a[INF],sz[INF],tot,head[INF],f[INF][INF][3],f1[INF][3],n;
void add_edge(int x,int y) {
    edge[++tot]=(_node_edge){y,head[x]};
    head[x]=tot;return ; 
}
void DFS(int x,int fa) {
    if (a[x]>0) {
        f[x][0][1]=a[x];
        f[x][0][0]=a[x];
    }
    else f[x][0][0]=a[x];
    sz[x]=1;
    for (int i=head[x];i;i=edge[i].next_) {
        int v=edge[i].to_;
        if (v==fa) continue;
        DFS(v,x);
        for (int k=0;k<=sz[x]+sz[v];k++) f1[k][0]=f1[k][1]=1e18;
        for (int j=sz[x];~j;j--)
            for (int k=sz[v];~k;k--) {
                f1[j+k][1]=min(f1[j+k][1],f[x][j][1]+f[v][k][1]);
                f1[j+k][0]=min(f1[j+k][0],min(f[x][j][0],f[x][j][1])+min(f[v][k][0],f[v][k][1]));
                if (f[v][k][0]<0 || f[v][k][1]<1e17) {
                    f1[j+k+1][0]=min(f1[j+k+1][0],f[x][j][0]);
                    f1[j+k+1][1]=min(f1[j+k+1][1],f[x][j][1]);
                }
            }

        for (int j=0;j<=sz[x]+sz[v];j++) 
            f[x][j][0]=f1[j][0],f[x][j][1]=f1[j][1];
        sz[x]+=sz[v];
    }
    return ;
}
signed main()
{
    memset(f,63,sizeof f);
    ios::sync_with_stdio(false);
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
        if (!a[i]) return 1;
    }
    for (int i=1;i<n;i++) {
        int x=0,y=0;cin>>x>>y;
        add_edge(x,y);add_edge(y,x);
    }
    DFS(1,0);
//  cout<<f[1][0][0]<<" "<<f[1][0][1]<<" endl\n";
    for (int i=0;i<=n;i++)
        if (f[1][i][0]<0 || f[1][i][1]<1e17) {cout<<i<<"\n";return 0;}
    return 0;
}