CF1182D代码MLE,急
  • 板块题目总版
  • 楼主TSY48
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/16 10:46
  • 上次更新2024/4/16 16:36:27
查看原帖
CF1182D代码MLE,急
684966
TSY48楼主2024/4/16 10:46
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define m_p make_pair
#define str string
#define lowbit(x) (x&(-x))
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
//typedef __int128 it;
const int Maxn=1e5+10;
const int inf=0x3f;
int n;
vector<int> e[Maxn],cnt[Maxn];
int deg[Maxn],dep[Maxn];
int siz[Maxn];
int mnsiz=1e9;
int rt,ech;
inline void getrt(int u,int fa)
{
    int mxsiz=-1;
    siz[u]=1;
    for(auto v:e[u]){
        if(v!=fa){
            getrt(v,u);
            mxsiz=max(mxsiz,siz[v]);
            siz[u]+=siz[v];
        }
    }
    mxsiz=max(mxsiz,n-siz[u]);
    if(mnsiz>mxsiz){
        mnsiz=mxsiz;
        rt=u;
    }
}
inline void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1;
    for(auto v:e[u]){
        if(v!=fa) dfs(v,u);
    }
}
inline bool check(int rot)
{
    dfs(rot,0);
    for(int i=1;i<=n;i++) cnt[i].clear();
    for(int i=1;i<=n;i++) cnt[dep[i]].pb(i);
    for(int i=1;i<=n;i++){
        if(!cnt[i].size()) continue;
        for(int j=1;j<(int)cnt[i].size();j++){
            if(deg[cnt[i][j]]!=deg[cnt[i][0]]) return false;
        }
    }
    return true;
}
inline int is_chain(int u)
{
    if(deg[u]>2) return 0;
    else if(deg[u]==1){
        ech=u;
        return 1;
    }
    for(auto v:e[u]){
        int len=is_chain(v);
        if(!len) return 0;
        else return len+1;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;scanf("%d%d",&u,&v);
        e[u].pb(v);e[v].pb(u);
        deg[u]++;deg[v]++;
    }
    getrt(1,0);
    if(check(rt)){
        printf("%d",rt);
        return 0;
    }
    bool ok=false;
    int filen;
    for(auto v:e[rt]){
        int len=is_chain(v);
        if(!len) continue;
        if(!ok){
            ok=true;
            filen=len;
            if(check(ech)){
                printf("%d",ech);
                return 0;
            }
        }
        else if(len!=filen){
            if(check(ech)){
                printf("%d",ech);
                return 0;
            }
        }
    }
    printf("-1");
    return 0;
}
2024/4/16 10:46
加载中...