萌新刚学oi求助
查看原帖
萌新刚学oi求助
232507
OK咯莫名其妙楼主2021/10/16 20:08
#include<bits/stdc++.h>
using namespace std;
const int maxn=400005;
int n;
struct node{
	int u,v;
	bool w; 
	int nxt;
}edge[maxn];
int head[maxn],tot,dp[maxn];
void add(int u,int v,bool w){
	edge[++tot].u=u;
	edge[tot].v=v;
	edge[tot].w=w;
	edge[tot].nxt=head[u];
	head[u]=tot;
}
void dfs(int u,int f){
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].v;
		if(v!=f){
			dfs(v,u);
			dp[u]+=dp[v]+edge[i].w;
		}
	}
}
void dfs2(int u,int f){
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].v;
		if(v!=f){
			if(edge[i].w==true){
				dp[v]+=dp[u]-1;
			}
			else
			dp[v]+=dp[u]+1;
			dfs2(v,u);
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int u,v;
		cin>>u>>v;
		add(u,v,false);
		add(v,u,true);
	}
	int min=2e9;
	for(int i=1;i<=n;i++){
		if(dp[i]<min)
			min=dp[i];
		else
		continue;
	}
	cout<<min<<endl;
	for(int i=1;i<=n;i++)
	{
		if(dp[i]==min)
			cout<<dp[i]<<" ";
	}
	return 0;
}
2021/10/16 20:08
加载中...