全WA 样例能过 悬关求调
  • 板块P1395 会议
  • 楼主znzryb
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/9/24 22:55
  • 上次更新2024/9/24 23:07:51
查看原帖
全WA 样例能过 悬关求调
1368189
znzryb楼主2024/9/24 22:55

用自己搞的例子也试了一下,好像是没问题的,不知道为什么全WA了

#include <iostream>
#include <vector>
using namespace std;
const int maxn=5e4+10;
int n,a,b,sonLenM[maxn];    // 最大子树长度
int core,minLenSon=maxn;
long long ans;
vector<int> g[maxn];
bool vis[maxn];
int dfs(int x,int dis) {
    ans+=dis;
    // cout<<x<<" "<<ans<<endl;
    bool isLeaf=true;
    int accMsonL;   // 接受到的子树最大长度
    for(vector<int>::iterator it=g[x].begin();it!=g[x].end();it++) {
        if(vis[*it]==false) {
            vis[*it]=true;
            int sonLen=dfs(*it,dis+1);
            accMsonL=max(sonLen,accMsonL);
            isLeaf=false;
        }
    }
    sonLenM[x]=max(accMsonL,dis);
    if(isLeaf) {
        sonLenM[x]=n-1;
        return 1;
    }else {
        return accMsonL+1;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n-1;i++) {
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vis[1]=true;
    dfs(1,0);
    for(int i=1;i<=n;i++) {
        if(sonLenM[i]<minLenSon)
            core=i,minLenSon=sonLenM[i];
    }
    fill(&vis[1],&vis[n+1],false);
    ans=0,vis[core]=true;
    dfs(core,0);
    cout<<core<<" "<<ans<<endl;
    return 0;
}
// 8
// 1 3
// 2 3
// 3 4
// 4 5
// 4 6
// 4 7
// 7 8
2024/9/24 22:55
加载中...