<h1 id="heading">题目</h1>
<p>{% raw %}</p>
<div><div class="fold_hider"><div class="close hider_title">点击显/隐题目</div></div><div class="fold">
    <div class="oj">   
        <div class="part" title="Description">
{% endraw %}
顺利潜入勺林寺几天后，方丈给了西瓜一个光荣而艰巨的任务——打扫寺庙中的道路。同时给了西瓜一张勺林寺的地图。  
西瓜这才知道，勺林寺中总共有n座房子，但道路只有n-1条，这n-1条道路连接了寺中的所有房子，即保证在任何两座房子都能沿着道路抵达。  
好在西瓜人缘不错，他知道每座房子中都有个自己的朋友，只要给他们每个人打个电话，让他到自己这里来，顺便把路也扫了，即给某座房子中的朋友打过电话后，可认为从该房子到西瓜所在的位置之间所有的道路都会被打扫干净。  
同时西瓜还知道，这n-1条道路中有一些路昨天已经被人打扫过了不需要再打扫一遍。  
现在西瓜想知道，自己最少要给多少个朋友打电话才能完成方丈给的任务。  
西瓜在编号为1的房子中。  
<p>{% raw %}<br>
</div><br>
<div class="part" title="Input"><br>
{% endraw %}</p>
<p>输入包含多组数据<br>
每组数据第一行包含一个n(2?≤?n?≤?10^5)，表示有n座房子<br>
之后n-1行，每行三个数字a，b，c表示在房子a和房子b之间有一条路，c等于1表示路已被打扫，c等于2表示路未被打扫。</p>
<p>{% raw %}<br>
</div><br>
<div class="part" title="Output"><br>
{% endraw %}</p>
<p>每组数据输出一个整数k，表示最少要给k个朋友打电话</p>
<p>{% raw %}<br>
</div><br>
<div class="samp"><br>
<div class="clear"></div><br>
<div class="input part" title="Sample Input"><br>
{% endraw %}</p>
<p>5<br>
1 2 2<br>
1 3 2<br>
1 4 2<br>
1 5 2</p>
<p>{% raw %}<br>
</div><br>
<div class="output part" title="Sample Output"><br>
{% endraw %}</p>
<p>4</p>
<p>{% raw %}<br>
</div><br>
<div class="clear"></div><br>
</div><br>
</div></p>
</div></div>
{% endraw %}

<h1 id="heading-1">题解</h1>
<p>根据题意画出图像,可以非常容易发现最终形成一棵以西瓜为树根的树<br>
朋友会一路清扫倒西瓜所在的房间,因此只有住在&quot;树叶&quot;的朋友有可能清扫</p>
<p>根据这个思路来分析每一个节点<br>
可以发现：</p>
<ol>
<li>如果从一个节点的子节点已经有 <code>a</code> 个朋友清扫,那么从该节点到树根都不需要再找朋友清扫</li>
<li>如果该节点的所有子节点都没有朋友清扫,那么如果从该节点到树根有需要清扫的路,只需要找一个朋友清扫即可</li>
</ol>
<p>因此可以发现,对于每一个节点,从树叶到该节点所需的最少朋友数只与其子节点有关,符合 <strong>动态规划</strong> 的特点,属于 <strong>树形dp</strong></p>
<p>用 <code>dp[i]</code> 表示从叶子到第 <code>i</code> 个节点的所需要最少的朋友数, <code>dp[1]</code> 即为答案<br>
有 <code>dp[i] = sum{ max(dp[j],Need_Clean) }</code> 其中 <code>j</code> 为 <code>i</code> 的所有子节点, <code>Need_Clean</code> 为道路 <code>(i,j)</code> 是否需要清扫</p>
<p>只需要一个 DFS 即可解决</p>
<h1 id="heading-2">代码</h1>
<div><div class="fold_hider"><div class="close hider_title">点击显/隐代码</div></div><div class="fold">```cpp 西瓜理发记(三) https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include<cstdio>
#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
<p>const int maxn = 1e5+5;</p>
<p>struct path{<br>
int u,v;<br>
bool k;<br>
path(int a,int b,int c):u(a),v(b),k(c){}<br>
};<br>
struct Node{<br>
list<path> children;<br>
int father;<br>
};</p>
<p>Node node[maxn];</p>
<p>int dfs(int t){<br>
int ans=0;<br>
for(list<path>::iterator it=node[t].children.begin();it!=node[t].children.end();it++){<br>
int tt = it-&gt;v;<br>
if(tt == node[t].father)<br>
continue;<br>
node[tt].father = t;<br>
ans += max(dfs(tt),(int)it-&gt;k);<br>
}<br>
return ans;<br>
}</p>
<p>int main(){<br>
cin.tie(0);<br>
cin.sync_with_stdio(false);</p>
<pre><code>int n;
while(cin &gt;&gt; n){
    for(int i=1;i&lt;=n;i++){
        node[i].father=-1;
        node[i].children.clear();
    }
         
    int a,b,c;
    for(int i=1;i&lt;n;i++){
        cin&gt;&gt;a&gt;&gt;b&gt;&gt;c;
        node[a].children.push_back(path(a,b,c-1));
        node[b].children.push_back(path(b,a,c-1));
    }   
    cout &lt;&lt; dfs(1) &lt;&lt; endl;
}
</code></pre>
<p>}</p>
<pre style="background-color:#fff">&lt;/div&gt;</pre>

AOJ 795.西瓜理发记(三)