CodeForces 77C Beavermuncher-0xFF （树形dp）

不错的树形dp。一个结点能走多次，树形的最大特点是到达后继的路径是唯一的，那个如果一个结点无法往子结点走，那么子结点就不用考虑了。

有的结点不能走完它的子结点，而有的可能走完他的子节点以后还会剩下一些点数。

影响走的次数的是当前结点的点数，因为往子结点走是一定要回来的，进入这个结点要花费这个结点一个点数，

剩下的点数k[i]-1就是往子结点走的最大次数，但是有可能会有剩余的点数。

可以这样处理，定义一个dp[i]表示花费一个点数进入i结点以后从它及其后代得到的最大价值，

根据这个定义，能走到的结点i的dp[i]至少为1，而且花费为1，如果有剩下的点数，对于i的父节点，想要得到剩下的点数，至少花费一个1点数才能得到1个点数。

不会比dp[i]更优，所以优先考虑选择dp[i]，对于同样的dp值优先选大的。

转移方程为dp[i] = {dp[j]}+cnt*2，|{dp[j]}|==min(k[i]-1,|{j}|)，cnt = min(k[u]-1-|{j}|,sum(left(j)))。

|{j}|表示后代数量,cnt是子节点后剩下的点数和后代结点剩下的点数的最小值。

当k[i]-1>|{j}|时可以选完后代的dp值，然后就要考虑选剩下的点数后代剩下的点数left(j)，

转移的时候还要维护一下left(i)。不能走到的点就不考虑了。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+;

typedef long long ll;

int k[maxn];

ll d[maxn];

vector<int> G[maxn];

#define PB push_back

bool cmp(int a,int b) { return a > b; }

ll dp(int u,int fa)

{

    if(d[u]>) return d[u];

    k[u]--;

    if(!G[u].size()|| !k[u]) {

        return d[u] = ;

    }

    vector<ll> opt;

    int cnt = ;

    for(int i = ; i < (int)G[u].size(); i++){

        int v = G[u][i];

        if(v == fa || !k[v]) continue;

        opt.PB(dp(v,u));

        cnt += k[v];

    }

    if(!opt.size()) return d[u] = ;

    int m = min(k[u],(int)opt.size());

    nth_element(opt.begin(),opt.begin()+m,opt.end(),cmp);

    k[u] -= m;

    d[u] = m;

    for(int i = ; i < m; i++){

        d[u] += opt[i];

    }

    if(k[u]>){

        m = min(k[u],cnt);

        k[u] -= m;

        d[u] += m<<;

    }

    return ++d[u];

}

int main()

{

    //freopen("in.txt","r",stdin);

    int n; scanf("%d",&n);

    for(int i = ; i <= n; i++) scanf("%d",k+i);

    for(int i = ; i < n; i++){

        int u,v; scanf("%d%d",&u,&v);

        G[u].PB(v); G[v].PB(u);

    }

    int s; scanf("%d",&s);

    k[s]++;

    printf("%I64d\n",dp(s,-)-);

    return ;

}

巴特西

CodeForces 77C Beavermuncher-0xFF （树形dp）

最新文章

热门文章