BZOJ_1785
一开始没有什么直接的思路，不过由于是棵树，而且K很小，也许是个树形的dp或者背包什么的，不过后来仔细一想，其实可以用贪心解决问题的。
对于一个非叶子节点，假设其若干子树中还有一些未配对的奶牛，那么应该是优先这些子树之间相互配对的，因为如果两个子树之间的两头奶牛可以配对但没有配对，而是有一个奶牛通过父亲甚至祖先和另外的奶牛配对了，这样不仅占有了当前这个节点的交换机的资源，还多占用了其父亲甚至祖先节点的交换机的资源，这样显然是划不来的。所以如果子树的奶牛之间可以相互配对，那么自然就先配好，剩下的奶牛再通过父节点传递出去。
大体的思路形成了，但不难发现还有一个小细节，一棵子树中可以有多个奶牛未配对吗？其实至多只会有一个奶牛配对，因为如果在满足交换机容量限制的前提下出现多个奶牛未配对，那么它们一定可以在子树中的某个交换机上就可以实现配对了。
我的程序里面f[i]表示的是当前一共完成了多少个配对，g[i]表示这个节点是否还剩余了1头奶牛尚未配对。
#include<stdio.h> #include<string.h> #define MAXD 100010 #define MAXM 200010 int N, K, D, first[MAXD], e, next[MAXM], v[MAXM], f[MAXD], g[MAXD]; void add(int x, int y) { v[e] = y; next[e] = first[x], first[x] = e ++; } void init() { memset(first, -1, sizeof(first[0]) * (N + 1)), e = 0; D = 0; for(int i = 1; i < N; i ++) { int x, y; scanf("%d%d", &x, &y); add(x, y), add(y, x); if(x == 1 || y == 1) ++ D; } } void dfs(int cur, int fa) { int flag = 0; f[cur] = 0, g[cur] = 0; for(int i = first[cur]; i != -1; i = next[i]) if(v[i] != fa) { flag = 1; dfs(v[i], cur); f[cur] += f[v[i]], g[cur] += g[v[i]]; } if(flag == 0) g[cur] = 1; else { if(g[cur] > 2 * K) f[cur] += K, g[cur] = 0; else f[cur] += g[cur] / 2, g[cur] &= 1; } } void solve() { dfs(1, -1); if(D == 1 && g[1]) ++ f[1]; printf("%d\n", f[1]); } int main() { while(scanf("%d%d", &N, &K) == 2) { init(); if(N == 1) printf("0\n"); else solve(); } return 0; }