CodeForces - 1098.DIV1.C： Construct a tree（贪心，构造）

Misha walked through the snowy forest and he was so fascinated by the trees to decide to draw his own tree!

Misha would like to construct a rooted tree with n

vertices, indexed from 1 to n, where the root has index 1. Every other vertex has a parent pi, and i is called a child of vertex pi. Vertex u belongs to the subtree of vertex v iff v is reachable from u while iterating over the parents (u, pu, ppu, ...). Clearly, v belongs to its own subtree, and the number of vertices in the subtree is called the size of the subtree. Misha is only interested in trees where every vertex belongs to the subtree of vertex 1

Below there is a tree with 6

vertices. The subtree of vertex 2 contains vertices 2, 3, 4, 5. Hence the size of its subtree is 4

The branching coefficient of the tree is defined as the maximum number of children in any vertex. For example, for the tree above the branching coefficient equals 2

. Your task is to construct a tree with n vertices such that the sum of the subtree sizes for all vertices equals s

, and the branching coefficient is minimum possible.

Input

The only input line contains two integers n

and s — the number of vertices in the tree and the desired sum of the subtree sizes (2≤n≤105; 1≤s≤1010

Output

If the required tree does not exist, output «No». Otherwise output «Yes» on the first line, and in the next one output integers p2

, p3, ..., pn, where pi denotes the parent of vertex i

Examples

Input

3 5

Output

Yes

1 1

Input

4 42

Output

No

Input

6 15

Output

Yes

1 2 3 1 5

Note

Below one can find one of the possible solutions for the first sample case. The sum of subtree sizes equals 3+1+1=5

, and the branching coefficient equals 2

Below one can find one of the possible solutions for the third sample case. The sum of subtree sizes equals 6+3+2+1+2+1=15

, and the branching coefficient equals 2

题意：给定N，S，让你构造一个大小为N的数，使得每个节点子树大小之和为S，如果存在，请构造一个树，使得儿子最多的点的儿子数量（P）最少。

思路：我们发现对于大小一定的树，越瘦长K越大（一条链，最大为N*(N+1)/2）,越矮胖越小（菊花树，最小为N+N-1），那么如果K不在这个范围我们输出-1；如果在，我们一定看i有构造一个满足题意的树。我们可以二分得到P。然后来构造。我的构造方式是先构造一条链，此时的sum=N*(N+1)/2；如果sum>S，我们就把最下面的点移到上面的某个位置，知道sum=S。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;ll N,S;

ll fa[maxn],q[maxn],d[maxn],head,tail,sz[maxn],son[maxn];

bool check(ll Mid)

{

    ll tN=N,now=,p=,res=;

    while(tN){

        res+=min(p,tN)*now;

        if(res>S) return false;

        tN-=min(p,tN);

        p*=Mid; now++;

    } return true;

}

int main()

{

    cin>>N>>S;

    ll Mn=N+N-; ll Mx=N*(N+)/;

    if(S<Mn||S>Mx) return puts("NO"),;

    ll L=,R=N-,Mid,res;

    while(L<=R){

        Mid=(L+R)/;

        if(check(Mid)) res=Mid,R=Mid-;

        else L=Mid+;

    }

    puts("YES");

    rep(i,,N) sz[i]=; ll Now=Mx,D=;

    for(int i=N;;i--){

        if(Now==S) break;

        if(sz[D]==sz[D-]*res) D++;

        if(Now-S>=i-D){

            sz[D]++; sz[i]--;

            Now-=(i-D);

        }

        else {

            sz[i]--; sz[i-(Now-S)]++;

            Now=S;

        }

    }

    head=tail=; q[head]=; d[]=;

    ll p=;

    rep(i,,N) {

        if(sz[i]==) break;

        L=p+; R=p+sz[i];

        rep(j,L,R){

            while(d[q[head]]!=i-||son[q[head]]==res){

                head++;

            }

            fa[j]=q[head]; son[q[head]]++;

            q[++tail]=j; d[j]=i;

        }

        p=R;

    }

    rep(i,,N) printf("%lld ",fa[i]);

    return ;

}

巴特西

CodeForces - 1098.DIV1.C： Construct a tree（贪心，构造）

最新文章

热门文章