连通块

最优题解

这题可以贪心的在树上求解。首先，叶子节点如果比m小，则肯定和父节点连在一起，如果当前节点结合它向下连通的节点综合大于等于m，则肯定切断和父亲节点的连接更好。按这个思路贪心求出最多可以划分的连通块数目和k做比较即可。
时间复杂度和空间复杂度都是

vector<int> g[200055];
int sum[200055];
int dfs(int u, int f, int m){
    int ans = 0;
    for(int v: g[u]){
        if(v == f) continue;
        ans += dfs(v, u, m);
        if(sum[v] < m) sum[u] += sum[v];
    }
    if(sum[u] >= m) ans++;
    return ans;
}
bool solve(int n, int k, int m, vector<int> &u, vector<int>&v, vector<int> &x){
    for(int i = 1; i <= n; ++i)
        g[i].clear(), sum[i] = x[i-1];
    assert(u.size() == n-1 && v.size() == n-1 && x.size() == n );
    for(int i = 0; i < n-1; ++i){
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    return dfs(1, 0, m) >= k;
}