社区讨论
深进代码有误?(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 条回复,欢迎继续交流。
正在加载回复...