东兴保卫战

小 W 在《三国演义》中读到东兴战役，对此非常感兴趣，在思考这场战役时他想出了一个问题。
东兴战场可以看成是一棵 $n$ 个节点的树，一开始每个节点上都没有军队。
现在魏吴两方轮流行动，吴国先手。两方每次行动都可以任意选择一个没有军队的节点并放上自己的军队，直到所有节点均被占领。
小 W 认为最终哪一方的军队占据的连通块个数多，哪一方就能取得优势。
设吴国的军队占据的连通块个数为 $A$ ，魏国的军队占据的连通块个数为 $B$ ，吴国的策略是希望 $A$ $-$ $B$ 最大，魏国的策略是希望 $A$ $-$ $B$ 最小。
他想知道在双方都选择最优策略的情况下， $A$ $-$ $B$ 会是多少？

using namespace std; #include <bits/stdc++.h> #define N 100005 int n; int d[N]; int main(){ scanf("%d",&n); for (int i=1;i<n;++i){ int u,v; scanf("%d%d",&u,&v); d[u]++,d[v]++; } sort(d+1,d+n+1); int ans=n&1,s=0; for (int i=1;i<=n;++i) s+=d[i]*(i&1?-1:1); ans+=s/2; printf("%d\n",ans); return 0; }

详情