【题目来源】
【题目描述】
小 v 所在的世界被规划成了树形结构，每一个节点上都可以建一个女仆咖啡厅或者桌游吧或者什么都不建。在确定点 1 为根节点之后，规划局要求：对于每一个非叶子的节点 i，设它子树（包括自己）中所有的女仆咖啡厅的数量为 cafe_i，桌游吧数目为 table_i，都有 cafe_i=table_i。
妹妹的问题是：这棵树最多能放多少个女仆咖啡厅。
【输入格式】
输入的第一行是，一个正整数 n，表示世界节点数。
第 2 至 n 行，每行两个正整数 u，v，表示 u 与 v 间有一条边。
【输出格式】
只有一行，最多能放的女仆咖啡厅的个数。
【输入样例】
5
1 2
2 3
3 4
2 5
【输出样例】
2
【数据范围】
对于 30% 的数据，保证 n≤20。
对于 100% 的数据，保证 1≤n≤10^5，1≤u,v≤n。
【算法分析】
● 本题是一道基础的“树形DP”问题。
● 理论上，一个节点的叶子节点数量可以是多个。但题目要求节点 u 的子树（含节点 u）中女仆咖啡厅的数量等于桌游吧的数量，这限制了子树的构建方式。所以，叶子节点只能独立存在，不能作为非叶子节点的子树的一部分。这是因为，如果叶子节点作为非叶子节点的子树，无法满足子树中女仆咖啡厅数量等于桌游吧数量（因为叶子节点只能只能代表 1 个位置，要么建“女仆咖啡厅”，或者建“桌游吧”，无法组合或拆分）。
● 本题代码如何判定叶子节点？本题代码采用”链式前向星“存树，将树中的每条无向边视为两条有向边进行存储。自然而然，就有了节点入度的陈述。分析可知，在此种设计下，当一个节点的入度为 1 且不是根节点时，此节点就是叶子节点。
● 在本文代码中，cnt 是一个计数器，用于统计当前节点 u 的子节点中叶子节点的数量。在 dfs 函数中，cnt 被初始化为 1，表示当前节点 u 本身可以被视为一个叶子节点（如果它没有子节点）。cnt/2 表示每两个叶子节点可以组成一个完整对（如 1 个“女仆咖啡厅”和 1 个“桌游吧”）。
● 约束条件：
（1）叶子节点处理：如果 i 是叶子节点，由于叶子节点无法作为非叶子节点的子树，因此可在叶子节点处自由选择建女仆咖啡厅、或桌游吧、或什么都不建。显然，为了最大化女仆咖啡厅，选择在叶子节点建女仆咖啡厅，此时 dp[i]=1，表示以 i 为根的子树最多能放的女仆咖啡厅的个数。
（2）非叶子节点处理：在非叶子节点的子树中，女仆咖啡厅的数目等于桌游吧的数目。这意味着对于非叶子节点，其子树中的女仆咖啡厅与桌游吧必须成对出现。
● 动态规划
（1）状态表示
dp[i]：表示以 i 为根的子树（含 i）最多能放的女仆咖啡厅的个数。
（2）状态计算（自底向上）
如果子节点 j 的入度 ind[j] 为 1，说明 j 是一个叶子节点，此时 cnt 增加 1。
如果子节点 j 不是叶子节点，则将子节点 j 的 dp 值累加到当前节点 u 的 dp 值中。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
int e[N<<1],ne[N<<1],h[N],idx;
int ind[N]; //in-degree
int dp[N];void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}void dfs(int u,int fa) {int cnt=1; //cnt of leaf nodes of u's childfor(int i=h[u]; i!=-1; i=ne[i]) {int j=e[i];if(j!=fa) {dfs(j,u);if(ind[j]==1) cnt++;else dp[u]+=dp[j];}}dp[u]+=cnt/2;
}int main() {memset(h,-1,sizeof h);int n;cin>>n;for(int i=1; i<n; i++) {int a,b;cin>>a>>b;add(a,b),add(b,a);ind[a]++,ind[b]++;}dfs(1,0);cout<<dp[1]<<endl;return 0;
}/*
in:
5
1 2
2 3
3 4
2 5out:
2
*/
【参考文献】