0分求助!!!
  • 板块P1395 会议
  • 楼主wangzhih
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/7/11 14:42
  • 上次更新2023/10/27 21:06:13
查看原帖
0分求助!!!
482095
wangzhih楼主2022/7/11 14:42

到底哪里错了啊,样例都没过...

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e4+5;
vector<int> t[MAXN];
int tot,nxt[MAXN*2],first[MAXN],to[MAXN*2],sum[MAXN],dp[MAXN],n;
//sum[i]:以i为根的子树的节点个数 dp[i]:以i为根的最大子树的节点数
//dp[i]=n-sum[i]
void add(int x,int y){//建边 
    nxt[++tot]=first[x];
    first[x]=tot;
    to[tot]=y;
}
void dfs(int now,int fa){
	sum[now]=1; 
	dp[now]=0;
	for(int e=first[now];e!=-1;e=nxt[e]){
		int u=to[e];//u:e的下一个 
		if(u==fa) continue;//下一个是父亲,跳出本次循环 
		dfs(u,now);//向深搜索 
		sum[now]+=sum[u];//sum加子树的节点 
		dp[now]=max(dp[now],sum[u]); 
	}
	dp[now]=max(dp[now],n-sum[now]);
}
int main(){
	memset(first,-1,sizeof(first));
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs(1,0);
	int flag=0,ans=0;
	for(int i=n-1;i>=0;i--)
		if(dp[i]>=ans){
			ans=dp[i];
			flag=i;
		}
	printf("%d %d",flag,ans);
	return 0;
}

谢谢有心人,回答我的问题

2022/7/11 14:42
加载中...