AtCoder ABC 259 F Select Edges

题意：

​ 给出一棵树，边带权，对于点i，最多保留d[i]条边，可以被分成连通块，请问边权和最大是多少

分析：

​ 因为可以被分成连通块，我们就可以对点i划分两种状态。第一种是点i不与父亲节点相连，那么他最多连接d[i] - 1条边；第二种是点i与父亲节点相连，那么他最多连接d[i]条边。

实现：

​ 我们可以用\(f[i][0 / 1]\)表示以i为根节点的子树，且节点i连接\((d[i] - 1) / d[i]\)条边的最大权值和

​ 自然答案就是\(f[1][1]\)。

​ 对于节点\(u\)，遍历他的儿子\(v\)，连接那些\(f[v][0] + w > f[v][1]\)的儿子\(v\)，意思是连接u的收益比他自己连边的收益更高，因为有\(d[u]\)条边的限制，把这些待加入的儿子放到一个set（sort）里优先取最大值。

总结：

​ 这种先加一种解，再判断是否补上差值的做法是贪心的常见实现方式。

#include <bits/stdc++.h>
    
using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x)    cout << x << endl;
#define SZ(x)    (int)x.size()
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, LL> PII;
const int inf = 0x3f3f3f3f;
void read(int &x) {int s = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) {f = (ch == '-' ? -1 : f); ch = getchar();} while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();} x = s * f;}

const int N = 300005;
int n;
vector<PII> g[N];
int d[N]; 
LL f[N][2]; //以i为根的子树，且边数小于d[i] / 小于等于d[i]

void dfs(int u, int fa)
{
    vector<LL> vec;
    for(PII e : g[u])
    {
        int v = e.first, w = e.second;
        if(v == fa) continue;
        dfs(v, u);
        vec.pb(f[v][0] + w - f[v][1]);
        f[u][0] += f[v][1], f[u][1] += f[v][1];
    }

    sort(all(vec)); 
    reverse(all(vec)); //贪心大到小

    for(int i = 0; i < SZ(vec); i ++)
    {
        if(vec[i] <= 0) break; //后面的不要了
        if(i < d[u] - 1)    f[u][0] += vec[i]; //加入的边不超过d[u] - 1
        if(i < d[u])    f[u][1] += vec[i];
    }

    if(!d[u])   f[u][0] = -2e18; //这条边不能被连接，负无穷
}

signed main()
{
    cin >> n;
    rep(i, 1, n + 1)    cin >> d[i];
    rep(i, 1, n)
    {
        int u, v;
        LL c;
        cin >> u >> v >> c;
        g[u].pb({v, c}); g[v].pb({u, c});
    }
    dfs(1, -1);
    cout << f[1][1] << '\n';
}