求助
  • 板块学术版
  • 楼主cyxg
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/1/18 16:01
  • 上次更新2023/10/24 03:43:14
查看原帖
求助
328413
cyxg楼主2023/1/18 16:01
#include<bits/stdc++.h>
using namespace std;
struct node{
	int next,to;
};
struct node e[1000012];
int f[100010],n,cnt,head[1000010],in[100010],st[100010],son[100010];
void dfs(int u){
	f[u]=1;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		dfs(v);
		f[u]+=f[v];
	//	cout<<f[u]<<"."<<v<<"."<<u<<endl;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>y>>x;
		e[++cnt].to=x;
		e[cnt].next=head[y];
		head[y]=cnt;
		in[x]++;son[y]++;
	}
	int root;int leaf;
	for(int i=1;i<=n;i++) {
	if(in[i]==0) root=i;f[i]=1,leaf++;}
//cout<<root<<endl;
f[root]=0;
	dfs(root);
	cout<<f[root]-1;
	return 0;
}

u142375树上统计

2023/1/18 16:01
加载中...