<h1 id="heading">题目</h1>
<p>{% fold 点击显/隐题目 %}</p>
<div class="oj"><div class="part" title="Description">
有一个n个节点n-1条边组成的树。
每个点看成一个人，连接u和v的边看成是“中意关系”，即u和v两个人都想和对方组队。每个人希望组队的对象有可能有多个。
一支队伍由且仅由两个人组成，并且如果u和v组队了，那么u、v将不能和其他人再组成一支队。
现在问你，这n个人最多能组成多少支队伍。（允许某些人组不了队）
一种可行的组队方案：
1与3组队
4与5组队
最多组成2支队
</div><div class="part" title="Input">
第一行输入一个整数n,m(1&lt;=n&lt;=200000)
接下来n-1行，每行两个整数u,v，表示u和v两个人都想和对方组队。
数据保证是一个合法的树。
</div><div class="part" title="Output">
输出一个整数，表示最多能组成多少支队伍。
</div><div class="samp"><div class="clear"></div><div class="input part" title="Sample Input">
5
1 2
1 3
2 4
4 5
</div><div class="output part" title="Sample Output">
2
</div><div class="clear"></div></div></div>
{% endfold %}

<h1 id="heading-1">题解</h1>
<p>下意识写了匈牙利算法,不过这道题会爆时间<br>
再仔细看一下题目<br>
可以发现其实求树上父节点和子节点配对能配多少对<br>
可以用动态规划求解</p>
<p>用<code>dp[t][0]</code>表示编号为<code>t</code>的节点往下并且不选取节点<code>t</code>能达到的最多对数<br>
用<code>dp[t][1]</code>表示编号为<code>t</code>的节点往下并且选取节点<code>t</code>能达到的最多对数</p>
<p>很容易就可以发现 <code>dp[t][0] = sum{ max(dp[child][0], dp[child][1])) }</code><br>
而 <code>dp[t][1]</code> 则根据是否存在没有选取的子节点(上一步有使用<code>dp[child][0]</code>)有<code>dp[t][1] = dp[t][0]</code> 和 <code>dp[t][1] = dp[t][0] + 1</code></p>
<h1 id="heading-2">代码</h1>
<p>{% fold 点击显/隐代码 %}```cpp 组队分配 <a href="https://github.com/OhYee/sourcecode/tree/master/ACM">https://github.com/OhYee/sourcecode/tree/master/ACM</a> 代码备份<br>
#include <cstdio><br>
#include <cstring><br>
#include <vector><br>
using namespace std;</p>
<p>const int maxn = 200005;</p>
<p>vector<int> e[maxn];<br>
int n;<br>
int parent[maxn];<br>
int dp[maxn][2];</p>
<p>void init() {<br>
memset(parent, 0, (n + 5) * sizeof(int));<br>
for (int i = 0; i &lt;= n; ++i)<br>
e[i].clear();<br>
}</p>
<p>void addEdge(int u, int v) {<br>
e[u].push_back(v);<br>
e[v].push_back(u);<br>
}</p>
<p>void dfs(int t) {<br>
// printf(&quot;dfs(%d)\n&quot;, t);<br>
dp[t][0] = dp[t][1] = 0;<br>
bool emptyChild = false;<br>
for (auto child : e[t]) {<br>
if (parent[t] != child) {<br>
parent[child] = t;<br>
dfs(child);<br>
if (dp[child][0] &lt; dp[child][1]) {<br>
dp[t][0] += dp[child][1];<br>
} else {<br>
emptyChild = true;<br>
dp[t][0] += dp[child][0];<br>
}<br>
}<br>
}<br>
dp[t][1] = dp[t][0] + emptyChild;<br>
// printf(&quot;dp[%d]={%d,%d}\n&quot;, t, dp[t][0], dp[t][1]);<br>
}</p>
<p>int main() {<br>
while (~scanf(&quot;%d&quot;, &amp;n)) {<br>
init();<br>
for (int i = 1; i &lt; n; ++i) {<br>
int a, b;<br>
scanf(&quot;%d%d&quot;, &amp;a, &amp;b);<br>
addEdge(a, b);<br>
}<br>
dfs(1);<br>
printf(&quot;%d\n&quot;, max(dp[1][0], dp[1][1]));<br>
}<br>
return 0;<br>
}</p>
<pre style="background-color:#fff">{% endfold %}</pre>

AOJ 911.组队分配