CF1098C Construct a tree

Solution

首先,我们考虑二分答案,先算出这个分支系数最小是多少,但难点就在于如何判断,首先我们知道,如果不考虑分支系数,$ s $ 的最小值为 $ 2\times n -1 $ ,最大值为 $ \frac{n\times(n-1) }{2} $ ,而前者的分支系数为 $ n-1 $ 后者的分支系数为 $ 1 $,一种是菊花图,一种是链,那这种构造方式是不是能给我们一点启发,就是我们可不可以算出在分支系数为 $ a $ 时,他的 $ s $ 的上限与下限的构造方案是不是一成不变的,而当我们求出了最小的分支系数过后,我们就可以开始真正的构造了。

我们首先可以发现,题目中的要求可以转化为 $ \sum_{i=1}^n dep_i=s $ ,也许你会问这样子转化一下有什么用处,但我们发现,如果题目中的要求转化成了这样,我们只需要更换一个点的深度就可以改变他整棵树的价值,而且可以做到,就是单纯 $ +1 $ ,但是我们发现,这样子是会 $ T $ 的,因为 $ s $ 的范围在 $ (0,10^{10}] $ ,那我们就要加速。我们考虑最左边的那条链为最终链,那么对于一个点,他改变一定是改变到最左边那条链,而改变的上限就是 $ sum-dep[now]+1 $ ,而 $ sum $ 就是那条最终链的长度。

Code

#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
  long long x=0,f=1;char ch=getchar();
  while(!isdigit(ch)&&ch!='-')ch=getchar();
  if(ch=='-')f=-1,ch=getchar();
  while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
  return x*f;
}
long long pow(long long x,long long y,long long p)
{
    long long ans=1;
    for (;y;y>>=1,x=x*x % p)
        if (y&1) ans=ans*x % p;
    return ans;
}
long long up,U,ww,aa[1001010],fre[1001010],ls[1001010],nw,id,deg[1001010],gg,j,dfn[1001010],di,fat[1001010],n,i,idd,dfnn[1001010],K,l,r,mid,ans,down,bb,dif,now,ed[1001010],sum,dep[1001010],e[1001010];
vector<int> edge[1001010];
bool exist[1001010];
void sc(int x,int fa)
{
	dep[x]=1;
	for (int i=0;i<edge[x].size();i++)
	    {
	    	int y=edge[x][i];
	    	if (dep[y]==0)
	    	    {
	    	    	sc(y,x);dep[x]+=dep[y];
				}
		}
}
long long calc(long long mid)
{
	for (i=1;i<=n;i++) edge[i].clear(),dep[i]=0;
    for (i=1;i<=n;i++) fre[i]=0;
    int nw=1;
    for (i=2;i<=n;i++)
         {
         	edge[nw].push_back(i);
         	fre[nw]++;
         	if (fre[nw]==mid) nw++;
		 }
	sc(1,0);
	long long ans=0;
	for (i=1;i<=n;i++) ans+=dep[i];
	return ans;
}
void sc_build(int x,int fa)
{
id++;dfnn[id]=x;
for (int i=0;i<edge[x].size();i++)
	if (edge[x][i]!=fa)
	 {
     	dep[edge[x][i]]=dep[x]+1;
     sc_build(edge[x][i],x);
     }
}
int main()
{
	//ios::sync_with_stdio(0);cin.tie();cout.tie();
    n=read();K=read();
    if ((K<2*n-1)||(K>n*(n+1)/2))
          {
          	puts("No");return 0;
		  }
	puts("Yes");
    l=1;r=n-1;
    while (l<=r)
         { 
         mid=(l+r)/2;
         if (calc(mid)<=K)
              {
              ans=mid;r=mid-1;
		      }
		  else l=mid+1;
		 }
	down=calc(ans);dif=K-down;bb=1;
//	cout<<dif<<endl;
	for (now=0;now<n;now+=bb,bb*=ans)
	    sum++,ed[sum]=now+1,exist[now+1]=true;
	     //cout<<"fuck"<<sum<<endl;
	for (i=1;i<=n;i++) edge[i].clear();
	for (i=1;i<=n;i++) fre[i]=0,dep[i]=0;
	dep[1]=1;
nw=1;
	for (i=2;i<=n;i++)
	     {
	     	edge[nw].push_back(i);deg[nw]++;deg[i]++;
	     	fat[i]=nw;
	     	fre[nw]++;
	     	if (fre[nw]==ans) nw++;
		 }
	sc_build(1,0);idd=sum;
	for (i=1;i<=n;i++)
	    if (exist[i]==false)
	       {
	       	gg++;up=dfnn[i];for (j=dfnn[i];j;j=fat[j]) up=j;
	       	U=max(U,dep[i]);
	       	if ((gg>1)&&(up==2))
	       	     {
	       	     	ww++;aa[ww]=i;
					}
			 }  
	for (i=U;i>=1;i--)
	     for (j=1;j<=ww;j++)
	         if (dep[aa[j]]==i)
	             {
	             	idd++;dfn[idd]=aa[j];exist[aa[j]]=true;
				 }
		ww=0;
		for (i=1;i<=n;i++)
		   if (exist[i]==false)
	       {
	       	gg++;up=dfnn[i];for (j=dfnn[i];j;j=fat[j]) up=j;
	       	U=max(U,dep[i]);
	       	if ((gg>1)&&(up!=2))
	       	     {
	       	     	ww++;aa[ww]=i;
					}
			 }  
	for (i=U;i>=1;i--)
	     for (j=1;j<=ww;j++)
	         if (dep[aa[j]]==i)
	             {
	             	idd++;dfn[idd]=aa[j];
				 }
    //sum:原先链的长度。
    //cout<<fat[2]<<endl;
    if (dif!=0)
        {
    for (i=sum+1;i<=n;i++)
        { 
        now=dfn[i];//cout<<now<<endl;
        if (dif>sum-dep[now]+1)  
             { 
             dif-=(sum-dep[now]+1);
             fat[now]=ed[sum];
             sum++;ed[sum]=now;
			 }
		else
		    { 
		    di=dep[now]+dif-1;
		    //cout<<ed[di]<<endl;
		    dif=0;
		    fat[now]=ed[di];break;
			}
		}
    }
    //cout<<"------"<<dif<<"------"<<endl;
for (i=2;i<=n;i++) printf("%d ",fat[i]);
    return 0;
}

上一篇:【生物应用】基于matlab粒子群算法酒的参数识别【含Matlab源码 1080期】


下一篇:construct binary tree 构造一棵二叉树