请大家帮忙看看,为什么会MLE
  • 板块P1395 会议
  • 楼主imldj
  • 当前回复5
  • 已保存回复5
  • 发布时间2020/8/19 11:57
  • 上次更新2023/11/6 19:57:01
查看原帖
请大家帮忙看看,为什么会MLE
312214
imldj楼主2020/8/19 11:57
#include<bits/stdc++.h>
using namespace std;
int dis[50010],n,x,y,dp[50010],ssize[50010];
vector<int> G[50010];
void work(int x){
    ssize[x]=1;
    for(int i=0;i<G[x].size();i++){
        int v=G[x][i];
        if(dis[i]) continue;
        dis[v]=dis[x]+1;
        work(v);
        ssize[x]+=ssize[v];
    }
}
void dfs(int x,int fa){
    dp[x]=dp[fa]-2*ssize[x]+n;
    for(int i=0;i<G[x].size();i++){
        int v=G[x][i];
        if(v!=fa) dfs(v,x);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dis[1]=1;
    work(1);
    int maxn=0,ans=1;
    for(int i=1;i<=n;i++) maxn+=dis[i]-1;
    dp[1]=maxn;
    dfs(1,0);
     for(int i=2;i<=n;i++){
        if(dp[i]<maxn) maxn=dp[i],ans=i;
    }
    printf("%d %d",ans,maxn);
    return 0;
}

谢谢!

2020/8/19 11:57
加载中...