C. Infected Tree -树形dp

题面

分析

开始直接贪心，每次找最大子树递归，结果出错了，要用树形dp进行计算，设 $d{p}_i$ 为当前可以拯救的最大数量，那么可以选择拯救其中一棵子树然后继续递归另一棵子树，所以状态转移方程就是 $d{p}_i=max(d{p}_i,total-d{p}_j+su{m}_j-1)$。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 3e5 + 10;

vector<int> adj[N];
int dp[N];
int sum[N];
bool st[N];

void dfs(int u, int fa) {
   
   // cout << u << endl;
    st[u] = true;
    int cnt = 0;
    for(auto j: adj[u]) {
   
        if(st[j]) continue;
        dfs(j, u);
        cnt += dp[j];
        sum[u] += sum[j];
    }
    for(auto j: adj[u]) {
   
        if(j == fa) continue;
        dp[u] = max(dp[u], cnt - dp[j] + sum[j] - 1);
    }
}

void solve() {
   
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) {
   
        adj[i].clear();
        st[i] = false;
        sum[i] = 1;
        dp[i] = 0;
    }
    for(int i = 0; i < n - 1; i ++) {
   
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
 ///   cout << "--------------\n";
    cout << dp[1] << "\n";
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T --) {
   
        solve();
    }
}