CF Valera and Elections
题目描述：
给你一棵树，每条边有2,1两种情况 每次可以选择一个点走到1点（根节点） 问最少选择几个点可以把边是2的点走完
分析：加入有一个条边是2 那么只需要找有没有子节点有2的边 有的话走子节点 没有的话走这个点 这个题比较特殊的是dfs遍历树 可以学习下存储方法;
ac代码：
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+2;
vector<int> Edge[MAX];
int anss[MAX],top=0;
int vis[MAX];
int dfs (int node,int flag){
// cout<<node<<endl;
vis[node]=1;
int len=Edge[node].size(),s=0,i;
for( i=0;i<len;i+=2){
if(vis[Edge[node][i]]==0){
if(Edge[node][i+1]==2) s+=dfs(Edge[node][i],1);
else s+=dfs(Edge[node][i],0);
}
}
// cout<<flag<<' '<<s<<' '<<node<<endl;
if(flag&&!s) {anss[top++]=node;return 1;}
return s;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("1.txt","r",stdin);
int n;
cin>>n;
for(int i=1;i<=n-1;i++){
int x,y,t;
cin>>x>>y>>t;
Edge[x].push_back(y);
Edge[x].push_back(t);
Edge[y].push_back(x);
Edge[y].push_back(t);
}
memset(vis,0,sizeof(vis));
dfs(1,0);
cout<<top<<endl;
if(top!=0){ cout<<anss[0];
for(int i=1;i<top;i++)
cout<<' '<<anss[i];
cout<<endl;}
}
投递新环境等公司8个岗位