CF 369C . Valera and Elections tree dfs 好题

The city Valera lives in is going to hold elections to the city Parliament.

The city has n districts and n - 1 bidirectional roads. We know that from any district there is a path along the roads to any other district. Let's enumerate all districts in some way by integers from 1 to n, inclusive. Furthermore, for each road the residents decided if it is the problem road or not. A problem road is a road that needs to be repaired.

There are n candidates running the elections. Let's enumerate all candidates in some way by integers from 1 to n, inclusive. If the candidate number i will be elected in the city Parliament, he will perform exactly one promise — to repair all problem roads on the way from the i-th district to the district 1, where the city Parliament is located.

Help Valera and determine the subset of candidates such that if all candidates from the subset will be elected to the city Parliament, all problem roads in the city will be repaired. If there are several such subsets, you should choose the subset consisting of the minimum number of candidates.

Input

The first line contains a single integer n (2 ≤ n ≤ 105) — the number of districts in the city.

Then n - 1 lines follow. Each line contains the description of a city road as three positive integers xi, yi, ti (1 ≤ xi, yi ≤ n,1 ≤ ti ≤ 2) — the districts connected by the i-th bidirectional road and the road type. If ti equals to one, then the i-th road isn't the problem road; if ti equals to two, then the i-th road is the problem road.

It's guaranteed that the graph structure of the city is a tree.

Output

In the first line print a single non-negative number k — the minimum size of the required subset of candidates. Then on the second line print k space-separated integers a1, a2, ... ak — the numbers of the candidates that form the required subset. If there are multiple solutions, you are allowed to print any of them.

Sample test(s)

input

output

1
5

input

output

1
3

input

output

4
5 4 3 2 



题意：
一个城市有n快区域，编号为1~n，这n块区域刚好是一个树的结构
有n-1条路，其中部分路是好的，部分是坏的，坏的路需要重修
现在城市要进行一个选举，要从n个候选人中选出部分人，这n个人也是编号为1~n
第i个人如果成功的话，他会把区域i到区域1之间的坏的道路修好
现在这个城市的人希望，从这个n个人选出一个尽量少的集合，并且这个集合可以把所有坏的路修好
如果方案不止一个，输出其中任意一个方案

明明是水题，我却做了很久（捂脸）

这道题相当于：
一棵树，以节点1为root
现在要从根节点引出尽量少的若干条路径，这些路径能够覆盖所有坏的边
然后输出路径的条数，和每条路径的终点节点

siz[i] : 以i为根的子树中， 坏的边的条数
son[i] : i的所有儿子节点j中，siz[j]最大的j就是son[i],即son[i]=max(siz[j])
use[i] : 若i为其中一条路径的终点，use[i]=true
print[i] : 为了方便输出答案的数组

2次dfs
dfs0 : 求出siz，son
dfs1 : 求出use

注意：当所有道路都是好的的时候，引出的路径为0条

  1 #include<cstdio>
  2 #include<cstring>
  3 
  4 using namespace std;
  5 
  6 const int maxn=1e5+5;
  7 inline int max(int a,int b)
  8 {
  9     return a>b?a:b;
 10 }
 11 
 12 struct Edge
 13 {
 14     int to,next,w;
 15 };
 16 Edge edge[maxn<<1];
 17 int head[maxn];
 18 int tot;
 19 int siz[maxn];
 20 int son[maxn];
 21 int use[maxn];
 22 int print[maxn];
 23 
 24 void addedge(int u,int v,int w)
 25 {
 26     edge[tot].to=v;
 27     edge[tot].w=w;
 28     edge[tot].next=head[u];
 29     head[u]=tot++;
 30 }
 31 
 32 void solve(int );
 33 void dfs0(int ,int );
 34 void dfs1(int ,int ,int );
 35 
 36 int main()
 37 {
 38     memset(head,-1,sizeof head);
 39     tot=0;
 40     int n;
 41     scanf("%d",&n);
 42     for(int i=1;i<n;i++)
 43     {
 44         int u,v,w;
 45         scanf("%d %d %d",&u,&v,&w);
 46         if(w>1)
 47             w=0;
 48         addedge(u,v,w);
 49         addedge(v,u,w);
 50     }
 51     solve(n);
 52     return 0;
 53 }
 54 
 55 void solve(int n)
 56 {
 57     memset(use,0,sizeof use);
 58     dfs0(1,0);
 59     dfs1(1,0,1);
 60     tot=1;
 61     for(int i=1;i<=n;i++){
 62         if(use[i])
 63             print[tot++]=i;
 64     }
 65     printf("%d
",tot-1);
 66     if(tot>1){
 67         for(int i=1;i<tot-1;i++)
 68             printf("%d ",print[i]);
 69         printf("%d
",print[tot-1]);
 70     }
 71 }
 72 
 73 void dfs0(int u,int pre)
 74 {
 75     siz[u]=0;
 76     son[u]=-1;
 77     for(int i=head[u];~i;i=edge[i].next)
 78     {
 79         int v=edge[i].to;
 80         if(v==pre)
 81             continue;
 82         int w=edge[i].w;
 83       if(!w)
 84         siz[u]++;
 85       dfs0(v,u);
 86       siz[u]+=siz[v];
 87       if(son[u]==-1||siz[v]>siz[son[u]])
 88         v=son[u];
 89     }
 90 }
 91 
 92 void dfs1(int u,int pre,int w)
 93 {
 94     if(!w)
 95         use[u]=true;
 96     if(!siz[u])
 97         return ;
 98     else{
 99         use[son[u]]=use[u];
100         use[u]=false;
101     }
102     for(int i=head[u];~i;i=edge[i].next)
103     {
104         int v=edge[i].to;
105         if(v==pre)
106             continue;
107         int w=edge[i].w;
108         dfs1(v,u,w);
109     }
110 }

View Code