A.C，codeforces 369C Valera and Elections

codeforces 369C Valera and Elections

###題目描述

n個節點和n - 1條雙向邊組成了一棵樹。這些邊分為兩種，一種類型為1，一種類型為2，類型為2的邊需要維修。當我們選中一個節點x時，節點x到節點1路徑上的所有類型為2的邊都會被維修。

A.C？我們需要找到n個節點的一個子集，滿足 子集中個數最少，并且所有類型為2的邊都得到維修

###分析

選擇該將哪個子樹的葉節點加入子集比較麻煩，所以就不糾結于葉節點了。對于節點x，它到父節點的邊為類型2，那么如果節點x的所有子樹都不存在類型為2的邊，則將節點x加入子集，否則任意一個子樹中的邊得到維修，x到父節點的邊也一定會被維修，這種情況x就不加入子集。

###代碼

<!-- lang: cpp -->
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define MAXN 100004int n, rnt;
vector<int> adj[MAXN];
int vis[MAXN], subset[MAXN];int dfs(int i, int flag)
{int j, s = 0;vis[i] = 1;for (j = 0; j < adj[i].size(); j += 2) {if (vis[adj[i][j]]) continue;if (adj[i][j + 1] == 2) s += dfs(adj[i][j], 1);else s += dfs(adj[i][j], 0);}if (flag && !s) {subset[rnt++] = i; return 1;}return s;
}int main()
{int i, a, b, t;while (cin >> n) {memset(vis, 0, sizeof(vis));memset(subset, 0, sizeof(subset));rnt = 0;for (i = 1; i <= n; i++) adj[i].clear();for (i = 0; i < n - 1; i++) {cin >> a >> b >> t;adj[a].push_back(b);adj[a].push_back(t);adj[b].push_back(a);adj[b].push_back(t);}dfs(1, 0);cout << rnt << endl;for (i = 0; i < rnt; i++)cout << subset[i] << " ";cout << endl;}return 0;
}