社区讨论

深进代码有误?(40pts)

P1395会议参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mcmz20rt
此快照首次捕获于
2025/07/03 13:55
8 个月前
此快照最后确认于
2025/11/04 06:47
4 个月前
查看原帖
我的代码都要和深入浅出改得一模一样了,怎么还是过不了,只有40pts?
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+100;
ll n,center,sum=0;
vector<ll> tr[N];
queue<ll> q;
ll sz[N],f[N],h[N];
void find(ll v,ll fa) {
	sz[v]=1,f[v]=0;
	for(int i=0; i<tr[v].size(); i++) {
		ll to=tr[v][i];
		if(to==fa)continue;
		find(to,v);
		sz[v]+=sz[to];
		if(sz[to]>f[v]) {
			f[v]=sz[to];
		}
	}
	f[v]=max(f[v],n-f[v]);
	if(f[v]<f[center]||(f[v]==f[center]&&v<center)) {
		center=v;
	}
}
void dfs() {
	q.push(center);
	while(!q.empty()) {
		ll v=q.front();
		q.pop();
		for(int i=0; i<tr[v].size(); i++) {
			ll to=tr[v][i];
			if(to==center)continue;
			if(h[to])continue;
			h[to]=h[v]+1;
			sum+=h[to];
			q.push(to);
		}
	}
}
int main() {
	cin>>n;
	for(int i=1; i<n; i++) {
		ll x,y;
		cin>>x>>y;
		tr[x].push_back(y);
		tr[y].push_back(x);
	}
	f[0]=INT_MAX;
	find(1,0);
	dfs();
	cout<<center<<" "<<sum;
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...