题一：输入n,a,b,c,d，n*n的表格，四种物品各有a,b,c,d个，求放的方案数。
组合数学，预处理C[m][n] = C[m-1][n-1] + C[m-1][n]
题二：一棵树，任选一个叶子节点，删除从叶子到根路径上的点，问最多生成几棵树。
感觉思路没什么问题，不过刚开始写复杂了，记录节点的入度即可，时间复杂度O(nlogn)
#include <iostream> #include <cstdio> #include <vector> #define LL long long using namespace std; const int maxn = 1e6+5; int n; vector<int> fa(maxn), a(maxn); int compt(int u){ int sum = 0; while(u != 0){ sum += a[u] - 1; u = fa[u]; } return sum; } int main(){ cin >> n; for(int i=1; i<n; i++){ int u, v; scanf("%d%d", &u, &v); fa[v] = u; a[u] ++; } fa[1] = 0; int ans = 0; for(int i=2; i<=n; i++) if(a[i] == 0){ ans = max(ans, compt(fa[i])); } cout << ans << endl; }
