● Codeforces Round #216 (Div. 2) - C. Valera and Elections

رفیق شما در کشوری زندگی می کند که در آستانه ی برگزاری انتخابات مجلس است.

این کشور، n استان و n-1 جاده(مسیر بین 2 استان) دارد و از هر استانی می توان از طریق تعدادی جاده به استانی دیگر رفت. هر استان از 1 تا n شماره گذاری شده و هر جاده از دو حالت خارج نیست: یا "راه سالم" است و یا "راه مشکل دار".

از میان نامزدهای انتخابات، کسی انتخاب می شود که به این وعده عمل کند: "من حداقل k و همچنین k استانی را می یابم که با تعمیر مسیرهای آن k استان منتهی به استان شماره 1 (مثلاً استان شماره 1 پایتخت آن کشور بوده)، هیچ راه مشکل داری در کشور ما وجود نداشته باشد".

حال یکی از فامیل های رفیق تان که در این انتخابات کاندید شده، از شما کمک می خواهد که در عملی شدن این وعده به او کمک کنید.

input

5
1 2 2
2 3 2
3 4 2
4 5 2

output

1
5

ورودی:

خط اوّل ورودی عدد طبیعی n نشان دهنده ی تعداد استان هاست.(n ≤ 10⁵)

در n-1 خط بعدی، در هر خط دو عدد x و y داده می شود(اعدادی از 1 تا n) که نشان می دهد استان x به استان y جاده دارد، و عدد t که نشان دهنده ی نوع جاده(سالم یا مشکل دار) است که از دو حالت خارج نیست: اگر سالم باشد 1 و اگر مشکل دار باشد 2 خواهد بود.

این تضمین شده است که ورودی داده شده، درخت(توضیح بیشتر) است.

خروجی:

به عنوان خروجی، عدد k (نشان دهنده ی کمینه ی تعداد استانهایی که با درست کردن مسیر آنها به استان 1، جاده ها همه سالم شود). حال در خط بعدی، شماره های k استان مورد نظر که به وسیله ی space از هم جدا شده اند را چاپ کنید!

نکته: جواب مسئله یکتا نیست و می تواند چند حالت داشته باشد که هر کدام از آنها به عنوان خروجی درست پذیرفته است و ترتیب چاپ کردن استان ها نیز اهمیتی ندارد.

// A Drop of the Programming Sea - adops.blog.ir

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

#define rout(n){cout << #n << endl; return 0;}
const unsigned int mxn = 1.e5+50;

vector<int> v[mxn];
vector<int> p[mxn];
bool mark[mxn];
vector<int> results;

inline int dfs(int k)
{
    bool badEdge = false;
    mark[k] = true;
    for(int i=0; i<v[k].size(); i++)
        if(!mark[v[k][i]])
        {
            if(dfs(v[k][i]))
                badEdge = true;
            else if(p[k][i]==2)
            {
                results.push_back(v[k][i]+1);
                badEdge = true;
            }
        }
    return badEdge;
}

int main()
{
    int n;
    cin >> n;
    for(int i=0; i<n-1; i++)
    {
        int x, y, type;
        cin >> x >> y >> type;
        x--, y--;
        v[x].push_back(y);
        v[y].push_back(x);
        p[x].push_back(type);
        p[y].push_back(type);
    }
    dfs(0);
    cout << results.size() << endl;
    for(int i=0; i<results.size(); i++)
	cout << results[i] << " ";
}