洛谷 P2996：[USACO10NOV] Visiting Cows G ← 邻接表 + 树形 DP + 树上最大权独立集

【题目来源】https://www.luogu.com.cn/problem/P2996【题目描述】经过了几周的辛苦工作Bessie 终于迎来了一个假期。作为奶牛群中最会社交的牛她希望去拜访 N(1≤N≤50000) 个朋友。这些朋友被标号为 1,2,…,N。这些奶牛有一个不同寻常的交通系统里面有 N−1 条路每条路连接了一对编号为 C1 和 C2 的奶牛 (1≤C1≤N1≤C2≤NC1≠C2 )。这样在每一对奶牛之间都有一条唯一的通路。FJ 希望 Bessie 尽快的回到农场。于是他就指示 Bessie如果对于一条路直接相连的两个奶牛Bessie 只能拜访其中的一个。当然Bessie 希望她的假期越长越好所以她想知道她可以拜访的奶牛的最大数目。【输入格式】第一行1 个整数 N。接下来 N−1 行每行 2 个整数 C1C2表示有一条通路连接了编号为 C1 和 C2 的奶牛。【输出格式】第一行1 个整数代表 Bessie 最多能拜访有多少头奶牛。​​​​​​​【输入样例】76 23 42 31 27 65 6【输出样例】4【数据范围】1≤N≤500001≤C1≤N1≤C2≤NC1≠C2【算法分析】● 本题与“洛谷 P1352没有上司的舞会https://blog.csdn.net/hnjzsyjyj/article/details/168026658”同模板且略简单。● 此题是树形动态规划的经典习题也是树上最大权独立集简单题。1状态定义f[u][0]不选 u 时以 u 为根的子树最大权。f[u][1]选 u 时以 u 为根的子树最大权。2转移方程u当前子树的根节点vu 的所有直接子节点val[u]节点 u 的权值f[u][0] Σ max(f[v][0], f[v][1])f[u][1] val[u] Σ f[v][0]【算法代码】#includebits/stdc.h using namespace std; const int N5e45; vectorint g[N]; long long f[N][2]; int n; void dfs(int u,int fa) { f[u][0]0; f[u][1]1; for(int v:g[u]) { if(vfa) continue; dfs(v,u); f[u][0]max(f[v][0],f[v][1]); f[u][1]f[v][0]; } } int main() { cinn; for(int i1; in; i) { int u,v; cinuv; g[u].push_back(v); g[v].push_back(u); } dfs(1,0); coutmax(f[1][0],f[1][1])endl; return 0; } /* in: 7 6 2 3 4 2 3 1 2 7 6 5 6 out: 4 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/168026658