https://vj.2vjd.cn/b02428b1bbcf4609f7b121c06ef01b09?v=1551834196**这是题目地址**
#include<cstring>
#include<algorithm>
using namespace std;
int n,u,v,Min,x,b,Min2;
int cnt,head[35000];
struct Edge{
int to,next;
}edge[35000];
int siz[35000],dp[35000],size[35000];
bool vis[35000];
void init(){
cnt=0;
Min=0x3f3f3f3f;
Min2=0x3f3f3f3f;
memset(head,-1,sizeof(head));
memset(siz,0,sizeof(siz));
memset(dp,0,sizeof(dp));
memset(vis,false,sizeof(vis));
for (int i=1;i<=35000;i++) size[i]=1;
}
void addEdge(int u,int v){
edge[cnt]=Edge{v,head[u]};
head[u]=cnt++;
edge[cnt]=Edge{u,head[v]};
head[v]=cnt++;
}
void dfs(int u,int p){
siz[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(v==p){
continue;
}
dfs(v,u);
siz[u]+=siz[v];
if(dp[u]<siz[v]){
dp[u]=siz[v];
}
}
dp[u]=max(dp[u],n-siz[u]);
Min=min(Min,dp[u]);
}
void dfs2(int x)
{
if(!vis[x])
{
vis[x]=1;
for(int i=head[x];i!=-1;i=edge[i].next)
{
int d=edge[i].to;
if(!vis[d])
{
dfs2(d);
size[x]+=size[edge[i].next];
}
}
}
}
void dfs3(int u,int p){
siz[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(v==p){
continue;
}
if (v==b) {
continue;
}
dfs3(v,u);
siz[u]+=siz[v];
if(dp[u]<siz[v]){
dp[u]=siz[v];
}
}
dp[u]=max(dp[u],Min-siz[u]);
Min2=min(Min2,dp[u]);
}
int main(void){
cin>>n;
init();
for(int i=0;i<n-1;i++){
cin>>u>>v;
addEdge(u,v);
}
dfs(1,-1);
for(int i=1;i<=n;i++){
if(dp[i]==Min) {b=i;dfs2(i);break;
}
}
for(int i=1;i<=n;i++) if (Min==size[i]) u=i;
memset(siz,0,sizeof(siz));
memset(dp,0,sizeof(dp));
dfs3(u,-1);
cout<<n-Min+Min2<<endl;
return 0;
}
我的思路是求两次重心,麻烦大佬帮我看看有啥问题,求重心算法我是抄别人的,不是很理解qwq。。