为什么还是错的呢,求调
查看原帖
为什么还是错的呢,求调
791994
liyanchenlycccccc楼主2023/8/8 09:24
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,h[N],to[N],nx[N],idx,d[N],v[N],t;
long long s=0,s1=0;
void add_edge(int u,int v)
{
  to[++idx]=v;
  nx[idx]=h[u];
  h[u]=idx;
}
void dfs(int u,int pig)
{
  for(int i=h[u]; i; i=nx[i])
  {
    int v=to[i];
    if(v==pig) continue;
    d[v]=d[u]+1;
    dfs(v,u);
  }
}
bool cmp(int x,int y)
{
  return x > y;
}
int main()
{
  scanf("%d",&n);
  for(int i=1; i<n; i++)
  {
    int u,v;
    scanf("%d%d",&u,&v);
    add_edge(u,v);
    add_edge(v,u);
  }
  d[1]=1;
  dfs(1,0);
  sort(d+1,d+n+1,cmp);
  for(int i=1; i<=n; i++)
    s+=d[i];
  if(s%2==1)
  {
    printf("-1");
  }
  else
  {
    t=s/2;
    for(int i=n; i>=1; i--)
    {
      if(s1+d[i]<=t)
      {
        s1+=d[i];
        v[d[i]]=1;
      }
    }
    for(int i=1; i<=n; i++) printf("%d ",v[i]);
  }
  return 0;
}
2023/8/8 09:24
加载中...