题解 P6213 【「SWTR-04」Collecting Coins】

z7z_Eta · 2020-05-11 11:14:21 · 题解

preface.

做法使用了树形dp一次dfs, 对 BeyondHeaven 的题解做了一定的简析与补充

提取题意.

选择一个d的联通子树(连通块), 并且选择一个点作入口. d 是小 c 所在的结点.
入口 r 满足 deg_r \le k_r-1 ; 其他点 v 满足 deg_v \le k_v .
求所有联通子树内的边权值和的最大价值.

官方题解的做法是令 r 做根, 用换根dp解决问题

然而比赛时发现了一种更通用的做法, 直接将入口 r 作为新的一维

我们以d为根, 状态记做f[u][0/1]
其中f[u][0]表示u子树中没有选择r的最大价值, f[u][1]则表示u子树中已选r

这样就保证了d在联通块内, 并且r被选到

于是, 题目变成了提高组dp

转移方程.

f[u][0] = \text{前}k[u]-1\text{大的}\{f[v][0]+val_{(u,v)}\}

f[u][1] = \begin{cases} 1.\text{前}k[u]-2\text{大的}\{f[v][0]+val_{(u,v)}\}\\ 2.\max_{x} \{ f[x][1]+val_{(u,x)}+\text{除}x\text{之外前}k[u]-2\text{大的}\{f[v][0]+val_{(u,v)}\}\} \end{cases}

(2.) 转移2.本质是枚举了x中出现了入口r

注意当k[u]=1时, f[u][1] = -\inf, 因为没有可选的儿子

因为d是根, k[d]需要先+1

所求即为f[d][1]

else.

由于排序, 复杂度 O(n \log n)

在 BeyondHeaven 的题解中, f[u][1]的转移没有考虑k[u]-1之外的, 所以有些瑕疵

code:

// Etavioxy
#define il inline
#define ll long long
#define rep(i,s,t) for(register int i=(s);i<=(t);i++)
#define rev_rep(i,s,t) for(register int i=(s);i>=(t);i--)
#define each(i,u) for(int i=head[u];i;i=bow[i].nxt)
#define pt(x) putchar(x)
using namespace std;
il int ci(){
    register char ch;int f=1;
    while(!isdigit(ch=getchar()))f=ch=='-'?-1:1;
    register int x=ch^'0';
    while(isdigit(ch=getchar()))x=(x*10)+(ch^'0');
    return f*x;
}

enum{N=100023};

struct Edge{ int nxt,to,val; } bow[N*2];
int head[N],tot_e;
il void add(int x,int y,int z){
    tot_e++;
    bow[tot_e<<1]=(Edge){head[x],y,z};
    bow[tot_e<<1|1]=(Edge){head[y],x,z};
    head[y]=(head[x]=tot_e<<1)|1;
}

int k[N];
int val[N],f[N][2];
bool cmp1(int x,int y){
    return f[x][0]+val[x] > f[y][0]+val[y];
}
void dfs(int u,int fa){
    if( k[u]==0 ){
        f[u][1] = -1e9;
        f[u][0] = 0;
        return ;
    }
    f[u][1] = f[u][0] = 0;
    vector<int>vec;
    each(i,u){
        int v = bow[i].to;
        if( v==fa ) continue;
        dfs(v,u);
        val[v] = bow[i].val;
        vec.push_back(v);
    }
    sort(vec.begin(),vec.end(),cmp1);
    bool flag=0;
    if( k[u]>(int)vec.size() ){ flag = 1; k[u] = vec.size(); }
    rep(i,0,k[u]-1) f[u][0] += f[vec[i]][0]+val[vec[i]];
    if( flag ) return f[u][1] = f[u][0], void();
    int kth = vec[k[u]-1];
    f[u][1] = f[u][0] - f[kth][0] - val[kth];
    rep(i,0,(int)vec.size()-1){
        if( i<=k[u]-1 ) f[u][1] = max(f[u][1],f[vec[i]][1]+f[u][0]-f[vec[i]][0]);
        else f[u][1] = max(f[u][1],f[vec[i]][1]+val[vec[i]]+f[u][0]-f[kth][0]-val[kth]);
    }
//  printf("LINE : %d u %d f %d %d\n",__LINE__,u,f[u][0],f[u][1]);
}

int main(){
    int n = ci(), d = ci();
    rep(i,1,n-1){
        int x = ci(), y = ci();
        add(x,y,ci());
    }
    rep(i,1,n) k[i] = ci()-1;
    k[d]++;
    dfs(d,0);
    printf("%d\n",f[d][1]);
    return 0;
}

这道题超优美的

~~但是Eta太蠢了太蠢了太蠢了~~