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
using namespace std;
const int N = 1e5+10;
int n,m,k,T;
struct node{
	int v,op;
	bool operator rhs.op;
	}
};
vector va[N];
int ans;
vector 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