首页 > 代码库 > Summer training round2 #6 (Training #26)
Summer training round2 #6 (Training #26)
A:树遍历 DFS 贪心 先从最远的点开始判
如果某个点连有的算上自身的junction不小于二就ans++ return 0
连有的算上自身的junction为一 就return 1
#include <bits/stdc++.h> #include <cstring> #include <iostream> #include <algorithm> #define INF 0x3f3f3f3f #define MOD 1000000007 #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!!\n") #define pb push_back #define pai pair<int,int> #define mid ((l+r)/2) #define lson l,mid,(rt<<1) #define rson mid+1,r,(rt<<1|1) //ugooo ll = long long; //ugooo ull= unsigned long long; //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pairint; const double eps=1e-8; const double PI=acos(-1); const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; const int maxn=200005; vector<int> t[maxn]; int a[maxn],f[maxn]; int ans=0; void dfs(int x,int pre) { int sum=0; int len=t[x].size(); for(int i=0;i<len;i++) { int aim=t[x][i]; if(aim==pre) continue; dfs(aim,x); sum+=a[aim]; } sum+=f[x]; if(sum>=2) { ans++; a[x]=0; } else if(sum==1) a[x]=1; else a[x]=0; } int main() { int n; cin >> n ; int from,to; for(int i=1;i<n;i++) { scanf("%d %d",&from,&to); t[from].pb(to); t[to].pb(from); } int m; cin >> m ; int now; for(int i=1;i<=m;i++) { scanf("%d",&now); f[now]=1; } dfs(1,-1); for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<endl; cout<<ans<<endl; return 0; }
B;SPFA
C:爆搜
D:并查集
E:模拟
Summer training round2 #6 (Training #26)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。