codeforces Valera and Elections (这思维题是做不明白了)

题目
题意: 给定一棵以1为根的树，有的边坏了。选择尽量少的点，这些点可以修复其到1的路径上坏的边。
思路: dfs。如果某个叶子对应的边恰好是坏的，那必定修复。之后我想的是从这里回溯到点1，把对应的边修好。但是时间复杂度高而且比较难实现。所以可以拿一个变量维护某个点对应的子树中是否存在点被选择过，这样即使他头上的边是坏的，也不会额外计数，而某个点对应子树中没有点被选过，他也是必选的。这种带返回值的dfs写的比较少，着实菜。
时间复杂度: O(n)
代码:

// Problem: C. Valera and Elections
// Contest: Codeforces - Codeforces Round #216 (Div. 2)
// URL: https://codeforces.com/problemset/problem/369/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,k,T;
struct node{
    
	int v,op;
	bool operator<(const node&rhs)
	{
    
		return op > rhs.op;
	}
};
vector<node> va[N];
int ans;
vector<int> res;
int dfs(int cur,int fa,int last) //上一条边
{
    
	bool t = 0; //是否有节点被选
	bool leaf = 1;
	for(auto tmp:va[cur])
	{
    
		int j = tmp.v;
		if(j==fa) continue; leaf = 0;
		int op = tmp.op;
		t |= dfs(j,cur,op);
	}
	// cout<<cur<<" "<<fa<<":"<<t<<endl;
	if(leaf&&last==2)
	{
    res.push_back(cur); return true;}
	if(!t && last==2) {
    res.push_back(cur); t = true;} //没有孩子选
	return t;
}
void solve()
{
    
	cin>>n;
	for(int i=0;i<n-1;++i)
	{
    
		int x,y,op; cin>>x>>y>>op;
		va[x].push_back({
    y,op}),va[y].push_back({
    x,op});
	}
	// for(int i=1;i<=n;++i) sort(va[i].begin(),va[i].end());
	dfs(1,0,1);
	cout<<res.size()<<"\n";
	for(int i=0;i<res.size();++i)
	{
    
		if(i) cout<<" ";
		cout<<res[i];
	}
}
signed main(void)
{
    
	solve();
	return 0;
}