AHU-795 西瓜理发记（三） (DFS)

Description

顺利潜入勺林寺几天后，方丈给了西瓜一个光荣而艰巨的任务——打扫寺庙中的道路。同时给了西瓜一张勺林寺的地图。
西瓜这才知道，勺林寺中总共有n座房子，但道路只有n-1条，这n-1条道路连接了寺中的所有房子，即保证在任何两座房子都能沿着道路抵达。
好在西瓜人缘不错，他知道每座房子中都有个自己的朋友，只要给他们每个人打个电话，让他到自己这里来，顺便把路也扫了，即给某座房子中的朋友打过电话后，可认为从该房子到西瓜所在的位置之间所有的道路都会被打扫干净。
同时西瓜还知道，这n-1条道路中有一些路昨天已经被人打扫过了不需要再打扫一遍。
现在西瓜想知道，自己最少要给多少个朋友打电话才能完成方丈给的任务。
西瓜在编号为1的房子中。

Input

输入包含多组数据
每组数据第一行包含一个n(2 ≤ n ≤ 10^5)，表示有n座房子
之后n-1行，每行三个数字a，b，c表示在房子a和房子b之间有一条路，c等于1表示路已被打扫，c等于2表示路未被打扫。

Output

每组数据输出一个整数k，表示最少要给k个朋友打电话

Sample Input

Sample Output

4

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e5 + 10;
 4 int f[maxn];
 5 
 6 struct node {
 7     int to, v;
 8 };
 9 
10 vector<node> T[maxn];
11 
12 int dfs(int a, int fa) {
13     int len = T[a].size(), b, c, ans;
14     if (len == 1 && T[a][0].to == fa) return f[a] = 0;
15     for (int i = 0; i < len; ++i) {
16         b = T[a][i].to;
17         if (b == fa) continue;
18         c = T[a][i].v;
19         ans = dfs(b, a);
20         if (c == 1) f[a] += ans;
21         else {
22             if (ans == 0) f[a] += 1;
23             else f[a] += ans;
24         }
25     }
26     return f[a];
27 }
28 
29 int main() {
30     int n, a, b, c;
31     while(~scanf("%d", &n)) {
32         for (int i = 1; i <= n; ++i) T[i].clear();
33         memset(f, 0, sizeof(f));
34         for (int i = 1; i < n; ++i) {
35             scanf("%d%d%d", &a, &b, &c);
36             T[a].push_back(node{b, c});
37             T[b].push_back(node{a, c});
38         }
39         printf("%d
", dfs(1, 0));
40     }
41     
42     return 0;
43 }