\(1.1\) \(Description\)

你有两棵有根树，每棵各有 n 个顶点。让我们用整数 1 到 n 给每棵树的顶点编

号。两棵树的根都是顶点 1。第一棵树的边都都是蓝色，第二棵树的边都是红色。

简明起见，我们称第一棵树是蓝色的，以及第二棵树是红色的。

当满足下面的两个条件下，我们认为边(x, y) 有害于边(p,q)：

1.边(x,y)的颜色不同于边(p,q)。

2.考虑与边(p, q) 颜色相同的树，编号为 x, y 的两个顶点中有且只有一个同时在

顶点 p 的子树与顶点 q 的子树里。

现在告诉你，在阶段 1，有恰好一条蓝色的边被删除了，

而在阶段 i，若我们删除了边(u 1 ，v 1 )， (u 2 ，v 2 )，… ， (u k ，v k )。

那么在阶段 i+1 我们要删除的所有满足以下条件的边(x,y):

1.边(x,y)未被删除。

2.存在一个 i(i ≤ k)使得边(x,y)有害于(u i ,v i )。

当某个阶段没有删除任何边时，则整个过程结束，你需要回答，每个阶段哪些边

将被删除。

注意，有害边的定义只依赖于开始删边之前的初始就拥有的两棵有根树。

\(1.2\) \(Task\)

\(1.2.1\) \(Input\)

输入第一行为整数 n，表示两棵树的顶点数目。

接下来的一行包含 n-1 个正整数a 2 ,a 3 ,…,a n (1 ≤ a i ≤ n;a i 不等于 i)，描述第一

棵树的边。数字a i 意味着第一棵树有一条边连接顶点a i 和顶点 i。

接下来的一行包含 n-1 个正整数b 2 ,b 3 ,…,b n (1 ≤ b i ≤ n;b i 不等于 i)，描述第二

棵树的边。数字b i 意味着第一棵树有一条边连接顶点b i 和顶点 i。

接下来的再一行包含一个整数 idx(1 ≤ idx < n)表示在第一阶段中删除的蓝树的

边的编号。我们让每棵树的每条边按照他们在输入中的前后顺序从 1 到 n-1 编

号。

\(1.2.2\) \(Output\)

对于每个阶段输出两行。如果这个阶段删除的边是蓝色的，那么对应这一阶段的

两行中，第一行必须为单词 Blue，否则为单词 Red。对应的第二行包含所有此阶

段删除的边的编号，按数字递增顺序输出。

\(1.3\) \(Sample\)

1.3.1 Input

5

1 1 1 1

4 2 1 1

3

1.3.2$ $Output

Blue

3

Red

1 3

Blue

1 2

Red

2

\(1.4\) \(Constraint\)

对于30%的数据，n<=10;

对于60%的数据，n<=1000。

对于100%的数据，n<=200000。

\(60分做法\)

直接O(n^2)枚举所有对应的边判断好坏，

然后随便模拟一下就好。

\(100分做法\)

考虑两棵树的dfs序。

假设要删红边（蓝边同理）：

考虑题目条件：设p是q的父亲，那么坏边的定义化为dfs序就是：

(id[x]>=id[q]&&id[x]<=id[q]+siz[q]-1)+(id[y]>=id[q]&&id[y]<=id[q]+siz[q]-1)==1

应该不用多解释。

令\(u[i]=min{id[x],id[y]},v[i]=max{id[x],id[y]}\)

发现每段待查区间的dfs序是连续的，可以想到用线段树维护区间信息。

我们开两颗线段树，一颗以u[x]为下标，每个区间用vector几下u[x]

在[l,r]区间的所有边的信息（这里说的（x,y）是红树上的边），以v[x]升序排列；

另一颗也差不多。

每次查询时，分别删去第一颗线段树vector里l<=u[i]<=r,且v[i]>r的部分（这一段在vector里是连续的一段，二分位置就好），

以及第二课线段树里l<=v[i]<=r,且u[i]<l的部分，这段也是连续的。

注意要判重，避免重复删除。

复杂度：

每条边在线段树里出现\(logn\)次，每次查询是O(log^2n的），每条边最多引发一次查询，

所以时间复杂度为O(nlog^2n)，空间复杂度为O(nlogn)。

很考验代码能力的一道题~~

#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
I read(int &res){
    res=0;re g=1;register char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')g=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        res=(res<<3)+(res<<1)+(ch^48);
        ch=getchar();
    }
    res*=g;
}
#define T e[k].to
typedef pair<int,int>pii;
int n,m,X,Y,P;
priority_queue<int>q1,q2;
namespace A{
    struct E{
        int to,nt;
    }e[202000];
    struct P{
        int x,y,id;
    }p[202000];
    inline bool bb1(P a,P b){
        return a.x==b.x?a.y<b.y:a.x<b.x;
    }
    inline bool bb2(P a,P b){
        return a.y==b.y?a.x<b.x:a.y<b.y;
    }
    vector<P>tr[808000],t[808000];int laz[808000],l1[808000];
    int head[202000],fa[202000],id[202000],siz[202000],vis[202000],tot;
    int cnt,s[4020000],sn;
    I add(int x,int y){
        e[++tot].to=y;
        e[tot].nt=head[x];
        head[x]=tot;
    }
    I D_1(int x){
        id[x]=++tot;siz[x]=1;//cout<<x<<":"<<id[x]<<endl;
        for(re k=head[x];k!=-1;k=e[k].nt){
            D_1(T);
            siz[x]+=siz[T];
        }
    }
    #define all 1,1,n
    #define lt k<<1,l,mid
    #define rt k<<1|1,mid+1,r
    I build(int k,int l,int r){
        if(l==r)return;
        re mid=(l+r)>>1;
        if(!tr[k].empty()){
            F(i,0,tr[k].size()-1){
                if(tr[k][i].x<=mid)tr[k<<1].emplace_back(tr[k][i]);
                else tr[k<<1|1].emplace_back(tr[k][i]);
            }
        }
        if(!t[k].empty()){
            F(i,0,t[k].size()-1){
                if(t[k][i].y<=mid)t[k<<1].emplace_back(t[k][i]);
                else t[k<<1|1].emplace_back(t[k][i]);
            }
        }
        build(lt);
        build(rt);
    }
    I modi(int k,int l,int r,int x,int y){
        if(x>r||y<l)return;
        if(x<=l&&r<=y){
            //cout<<"h"<<tr[k].size()<<" "<<t[k].size()<<endl;
            re posl,posr,mid;
            if(!tr[k].empty()){
                posl=0,posr=tr[k].size()-1;
                while(posl!=posr){
                    mid=(posl+posr)>>1;
                    if(tr[k][mid].y<=y)posl=mid+1;
                    else posr=mid;
                }
                if(tr[k][posl].y>y){
                    F(j,posl,tr[k].size()-1){
                        s[++cnt]=tr[k][j].id;
                    //  cout<<"@"<<tr[k][j].x<<" "<<tr[k][j].y<<endl;
                    }
                    tr[k].erase(tr[k].begin()+posl,tr[k].begin()+(tr[k].size()-1));
                }
            }
            if(!t[k].empty()){
                posl=0;posr=t[k].size()-1;
                while(posl!=posr){
                    mid=(posl+posr+1)>>1;
                    if(t[k][mid].x>=x)posr=mid-1;
                    else posl=mid;
                }
                if(t[k][posl].x<x){
                    F(j,0,posl){
                        s[++cnt]=t[k][j].id;
                    //  cout<<"$"<<t[k][j].x<<" "<<t[k][j].y<<endl;
                    }
                    t[k].erase(t[k].begin()+0,t[k].begin()+posl);
                }

            }
            return;
        }
        re mid=(l+r)>>1;
        modi(lt,x,y);modi(rt,x,y);
    }
    IN print(){
        sn=0;
        sort(s+1,s+1+cnt);
        F(i,1,cnt){
            if(!vis[s[i]]){
                if(!sn){
                    sn=1;printf("Blue\n");
                }
                vis[s[i]]=1;
                q1.push(s[i]);
                printf("%d ",s[i]);
            }
        }
        if(sn)printf("\n");
        return sn;
    }
    I init(){
        memset(head,-1,sizeof(head));
        tot=0;
        F(i,2,n){
            read(fa[i]);
            add(fa[i],i);
        }
        tot=0;
        D_1(1);
    }
    I init2(){
        sort(p+1,p+n,bb2);
        F(i,1,n-1){
            tr[1].emplace_back(p[i]);
        }
        sort(p+1,p+n,bb1);
        F(i,1,n-1){
            t[1].emplace_back(p[i]);
        }
        build(all);
        F(i,2,n){
            p[i-1].x=fa[i];p[i-1].y=i;p[i-1].id=i-1;
        }
    }
};
namespace B{
    struct E{
        int to,nt;
    }e[202000];
    struct P{
        int x,y,id;
    }p[202000];
    inline bool bb1(P a,P b){
        return a.x==b.x?a.y<b.y:a.x<b.x;
    }
    inline bool bb2(P a,P b){
        return a.y==b.y?a.x<b.x:a.y<b.y;
    }
    vector<P>tr[808000],t[808000];int laz[808000],l1[808000];
    int head[202000],fa[202000],id[202000],siz[202000],vis[202000],tot;
    int cnt,s[4040000],sn;
    I add(int x,int y){
        e[++tot].to=y;
        e[tot].nt=head[x];
        head[x]=tot;
    }
    I D_1(int x){
        id[x]=++tot;siz[x]=1;//cout<<x<<":"<<id[x]<<endl;
        for(re k=head[x];k!=-1;k=e[k].nt){
            D_1(T);
            siz[x]+=siz[T];
        }
    }
    #define all 1,1,n
    #define lt k<<1,l,mid
    #define rt k<<1|1,mid+1,r
    I build(int k,int l,int r){
        if(l==r)return;
        re mid=(l+r)>>1;
        if(!tr[k].empty()){
            F(i,0,tr[k].size()-1){
                if(tr[k][i].x<=mid)tr[k<<1].emplace_back(tr[k][i]);
                else tr[k<<1|1].emplace_back(tr[k][i]);
            }
        }
        if(!t[k].empty()){
            F(i,0,t[k].size()-1){
                if(t[k][i].y<=mid)t[k<<1].emplace_back(t[k][i]);
                else t[k<<1|1].emplace_back(t[k][i]);
            }
        }
        build(lt);
        build(rt);
    }
    I modi(int k,int l,int r,int x,int y){
        if(x>r||y<l)return;
        if(x<=l&&r<=y){
        //  cout<<"H"<<tr[k].size()<<" "<<t[k].size()<<endl;
            re posl,posr,mid;
            if(!tr[k].empty()){
                posl=0,posr=tr[k].size()-1;
                while(posl!=posr){
                    mid=(posl+posr)>>1;
                    if(tr[k][mid].y<=y)posl=mid+1;
                    else posr=mid;
                }
                if(tr[k][posl].y>y){
                    F(j,posl,tr[k].size()-1){
                        s[++cnt]=tr[k][j].id;
                    //  cout<<"@"<<tr[k][j].x<<" "<<tr[k][j].y<<endl;
                    }
                    tr[k].erase(tr[k].begin()+posl,tr[k].begin()+(tr[k].size()-1));
                }
            }
            if(!t[k].empty()){
                posl=0;posr=t[k].size()-1;
                while(posl!=posr){
                    mid=(posl+posr+1)>>1;
                    if(t[k][mid].x>=x)posr=mid-1;
                    else posl=mid;
                }
                if(t[k][posl].x<x){
                    F(j,0,posl){
                        s[++cnt]=t[k][j].id;
                    //  cout<<"$"<<t[k][j].x<<" "<<t[k][j].y<<endl;
                    }
                    t[k].erase(t[k].begin()+0,t[k].begin()+posl);
                }

            }
            return;
        }
        re mid=(l+r)>>1;
        modi(lt,x,y);modi(rt,x,y);
    }
    IN print(){
        if(!cnt)return 0;
        sn=0;
        sort(s+1,s+1+cnt);
        F(i,1,cnt){
            if(!vis[s[i]]){
                if(!sn){
                    sn=1;printf("Red\n");
                }
                vis[s[i]]=1;
                q2.push(s[i]);
                printf("%d ",s[i]);
            }
        }
        if(sn)printf("\n");
        return sn;
    }
    I init(){
        memset(head,-1,sizeof(head));
        tot=0;
        F(i,2,n){
            read(fa[i]);
            add(fa[i],i);
        }
        tot=0;
        D_1(1);
    }
    I init2(){
        sort(p+1,p+n,bb2);
        F(i,1,n-1){
            tr[1].emplace_back(p[i]);
        }
        sort(p+1,p+n,bb1);
        F(i,1,n-1){
            t[1].emplace_back(p[i]);
        }
        build(all);
        F(i,2,n){
            p[i-1].x=fa[i];p[i-1].y=i;p[i-1].id=i-1;
        }
    }
};
I init(){
    F(i,2,n){
        A::p[i-1].x=min(B::id[A::fa[i]],B::id[i]),A::p[i-1].y=max(B::id[A::fa[i]],B::id[i]);A::p[i-1].id=i-1;
        B::p[i-1].x=min(A::id[B::fa[i]],A::id[i]),B::p[i-1].y=max(A::id[B::fa[i]],A::id[i]);B::p[i-1].id=i-1;
    }
    A::init2();
    B::init2();
}
int main(){
    freopen("two.in","r",stdin);
    freopen("two.out","w",stdout);
    read(n);
    A::init();
    B::init();
    init();
    read(P);
    q1.push(P);
    printf("Blue\n%d\n",P);
    A::vis[P]=1;
    m=0;
    while(1){
        m++;
        if(m&1){
            B::cnt=0;
            while(!q2.empty())q2.pop();
            while(!q1.empty()){
            //  cout<<"Q:"<<A::p[q1.top()].y<<" "<<A::id[A::p[q1.top()].y]<<" "<<A::id[A::p[q1.top()].y]+A::siz[A::p[q1.top()].y]-1<<endl;
                B::modi(all,A::id[A::p[q1.top()].y],A::id[A::p[q1.top()].y]+A::siz[A::p[q1.top()].y]-1),q1.pop();
            }
            if(!B::print())break;
        }
        else {
            A::cnt=0;
            while(!q1.empty())q1.pop();
            while(!q2.empty()){
            //  cout<<"q:"<<B::p[q2.top()].y<<" "<<B::id[B::p[q2.top()].y]<<" "<<B::id[B::p[q2.top()].y]+B::siz[B::p[q2.top()].y]-1<<endl;
                A::modi(all,B::id[B::p[q2.top()].y],B::id[B::p[q2.top()].y]+B::siz[B::p[q2.top()].y]-1),q2.pop();
            }
            if(!A::print())break;
        }
    }
    return 0;
}
/*
5
1 1 1 1
4 2 1 1
3
*/

\(30分做法\)

枚举根节点，暴力dfs即可。复杂度O(n^2)。

\(100分做法\)

看到这种询问整棵树的信息的题，容易想到点分治。

设当前重心为u。

考虑30分做法的dfs，我们需要维护sum(括号序列前缀和），

cnt（合法划分的个数）。

这里我们要把两个残缺的括号序列拼起来，问题就变成了

如何记录一个残缺的括号序列的合法划分数，以及如何判断其合法性。

我们把待合并的两个括号序列分别叫左序列和右序列。

手膜一下，发现一个性质：对于一个前缀和为sum的左序列，其合法条件为：

这个序列的任意后缀的前缀和（也就是从u到这个节点的过程中的所有前缀和）都<=sum。

而其合法段数cnt即为这个序列所有后缀=sum的个数和-1。

右序列也可以发现类似的性质。

由此，我们可以做两次dfs，求解所有合法的左序列f,右序列g。

每个序列都可以表示为一个二元组（sum,cnt）,sum就是前缀和的绝对值，cnt就是

合法划分数。合并时，对答案k的贡献就是\(\sum_{i=0}^k\)\(f[sum][i]*g[sum][k-i]\)

发现这个东西是卷积的形式，直接用fft搞就好。

#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
I read(int &res){
    res=0;re g=1;register char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')g=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        res=(res<<3)+(res<<1)+(ch^48);
        ch=getchar();
    }
    res*=g;
}
typedef double db;
const db pi=acos(-1);
const int INF=1e9+7;
int r[50500];
struct CPX{
    db x,y;
    CPX(db _x=0.0,db _y=0.0){
        x=_x;y=_y;
    }
    friend CPX operator + (CPX a,CPX b){
        register CPX c;
        c.x=a.x+b.x;
        c.y=a.y+b.y;
        return c;
    }
    friend CPX operator - (CPX a,CPX b){
        register CPX c;
        c.x=a.x-b.x;
        c.y=a.y-b.y;
        return c;
    }
    friend CPX operator * (CPX a,CPX b){
        register CPX c;
        c.x=a.x*b.x-a.y*b.y;
        c.y=a.x*b.y+a.y*b.x;
        return c;
    }
    CPX operator / (const db val){
        register CPX c;
        c.x=x/val;c.y=y/val;
        return c;
    }
};
I fft(CPX b[],int n,int sit){
    for(re i=0,j=0;i<n;i++){
        if(i<j)swap(b[i],b[j]);
        re k=n>>1;
        while(k&j)j^=k,k>>=1;
        j^=k;
    }
    for(re i=1;i<n;i<<=1){
        CPX w1=CPX(cos(pi/i),sin(pi/i)*sit);
        for(re j=0;j<n;j+=(i<<1)){
            CPX w=CPX(1,0);
            for(re l=j,r=j+i;l<j+i;l++,r++,w=w*w1){
                CPX t=b[r]*w;
                b[r]=b[l]-t;
                b[l]=b[l]+t;
            }
        }
    }
    if(sit==-1){
        F(i,0,n-1){
            b[i]=b[i]/n;
        }
    }
}
struct E{
    int to,nt,v;
}e[101000];
#define T e[k].to
char c[50500];
vector<int>f[50500],g[50500];
int n,m,N,maxi,root,fmx,gmx,dep[50500],f0[50500],g0[50500],lg[50500],gl[50500],vis[50500],siz[50500],mx[50500],head[50500],a[50500],tot=-1,X,Y;
ll ans[50500];
I D_3(int x,int fa){
    siz[x]=1;dep[x]=1;
    for(re k=head[x];k!=-1;k=e[k].nt){
        if(T==fa||vis[T]||e[k].v)continue;
        D_3(T,x);
        siz[x]+=siz[T];
        dep[x]=max(dep[x],dep[T]+1);
    }
}
I findroot(int x,int fa){
    siz[x]=1;mx[x]=0;
    for(re k=head[x];k!=-1;k=e[k].nt){
        if(T==fa||vis[T]||e[k].v)continue;
        findroot(T,x);
        siz[x]+=siz[T];
        mx[x]=max(mx[x],siz[T]);
    }
    mx[x]=max(mx[x],N-siz[x]);
    if(maxi>mx[x]){
        maxi=mx[x];
        root=x;
    }
}
I D_1(int x,int fa=0,int sum=0,int cnt=1,int maxsiz=0){
    sum+=a[x];
    if(sum==maxsiz)cnt++;
    if(sum>maxsiz)maxsiz=sum,cnt=1;
    if(sum==maxsiz)f[sum].emplace_back(cnt-1+(sum!=0));
    for(re k=head[x];k!=-1;k=e[k].nt){
        if(T==fa||vis[T]||e[k].v)continue;
        D_1(T,x,sum,cnt,maxsiz);
    }
}
I D_2(int x,int fa=0,int sum=0,int cnt=1,int minsiz=0){
    sum+=a[x];
    if(sum==minsiz)cnt++;
    if(sum<minsiz)minsiz=sum,cnt=1;
    if(sum==minsiz)g[-sum].emplace_back(cnt-1);
    for(re k=head[x];k!=-1;k=e[k].nt){
        if(T==fa||vis[T]||e[k].v)continue;
        D_2(T,x,sum,cnt,minsiz);
    }
}
I calc(int depth,int sit){
    static CPX A[101000],B[101000];
    F(i,0,depth){
        re len1,len2,len;
        len1=len2=len=1;
        for(auto p:f[i])A[p].x++,len1=max(len1,p+1);
        f[i].clear();
        for(auto p:g[i])B[p].x++,len2=max(len2,p+1);
        g[i].clear();
        while(len<len1+len2-1)len<<=1;
        fft(A,len,1);
        fft(B,len,1);
        F(i,0,len-1){
            A[i]=A[i]*B[i];
        }
        fft(A,len,-1);
        F(i,0,len1+len2-1){
            //cout<<"!"<<i<<"";
            ans[i]+=1ll*sit*(ll)floor(A[i].x+0.5);
            //cout<<ans[i]<<endl;
        }
        memset(A,0,sizeof(CPX)*len);
        memset(B,0,sizeof(CPX)*len);
    }
}
I solve(int x){
    D_3(x,0);
    for(re k=head[x];k!=-1;k=e[k].nt){
        if(vis[T]||e[k].v)continue;
        D_1(T,x);
    }
    f[0].push_back(0);
    D_2(x);
    calc(dep[x],1);
    for(re k=head[x];k!=-1;k=e[k].nt){
        if(vis[T]||e[k].v)continue;
        D_1(T,x);
        D_2(T,x,a[x],1,min(a[x],0));
        calc(dep[T]+1,-1);
    }
}
I divided(int x){
    solve(x);
    vis[x]=1;
    for(re k=head[x];k!=-1;k=e[k].nt){
        if(vis[T]||e[k].v)continue;
        e[k].v=e[k^1].v=1;
        N=siz[T];
        maxi=INF;
        findroot(T,x);
        divided(root);
    }
}
int main(){
    freopen("bracket.in","r",stdin);
    freopen("bracket.out","w",stdout);
    read(n);
    tot=-1;
    memset(head,-1,sizeof(head));
    F(i,1,n-1){
        read(X);read(Y);
        e[++tot].to=Y;
        e[tot].nt=head[X];
        head[X]=tot;
        e[++tot].to=X;
        e[tot].nt=head[Y];
        head[Y]=tot;
    }
    F(i,1,n){
        cin>>c[i];
        a[i]=(c[i]=='(')?1:-1;
    }
    N=n;maxi=INF;
    findroot(1,0);
    divided(root);
    read(m);
    while(m--){
        read(X);
        printf("%lld\n",ans[X]);
    }
    return 0;
}
/*
6
1 2
2 6
4 2
3 4
1 5
)
(
)
)
(
)
3
1
2
3
*/

话说80分是真滴良心啊。

\(80分做法\)

首先，肯定要尽量多的选质数，然后选合数的话，

其质因子也不能超过2个。且一个<= √n,一个>= √n

跑个费用流就好。

。。。满分做法待填坑，先提供std代码一份：

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=400005,M=400005,inf=1047483647;
struct node { int y,z,c,next; } a[M<<2];
LL dis[M],an;
int b[M],la[M],d[M],q[M+100],D[N],pr[N],head[M],i,j,k,n,m,J,s,e,z,X,l,r,g;
bool p[N];
char c;

inline char getc()
{
    #define VV 10000000
    static char s[VV],*l=s,*r=s;
    if (l==r)
        l=s,r=s+fread(s,1,VV,stdin);
    return *l++;
}

int read(){ int z=0; do c=getchar(); while (c<'0'||c>'9'); while (c>='0'&&c<='9') z*=10,z+=c-'0',c=getchar(); return z; }

void jb(int x,int y,int z,int c)
{
    a[++k]=(node){y,z,c,head[x]},head[x]=k,
    a[++k]=(node){x,0,-c,head[y]},head[y]=k;
}

int plus(int z){ return z<M+50?z+1:1; }

bool SPFA()
{
    for (register int i=1;i<=e;++i) dis[i]=-inf,p[i]=0;
    p[q[l=r=1]=s]=1,dis[s]=0;
    for (;l!=plus(r);l=plus(l))
    {
        int d=q[l];
        for (register int j=head[d];j;j=a[j].next)
            if (a[j].z)
            {
                int c=a[j].y;
                if (dis[c]<dis[d]+a[j].c)
                {
                    dis[c]=dis[d]+a[j].c,la[c]=d,b[c]=j;
                    if (!p[c])
                        p[q[r=plus(r)]=c]=1;
                }
            }
        p[d]=0;
    }
    return dis[e]>0;
}

void addflow()
{
    for (register int i=e;i!=s;i=la[i]) --a[b[i]].z,++a[b[i]^1].z;
    an+=dis[e];
}

int main(){
    freopen("sum.in","r",stdin);
    freopen("sum.out","w",stdout);
    n=read();
    X=sqrt(n);
    for (i=2;i<=n;++i)
    {
        if (!p[i]) pr[++g]=i;
        for (j=1;j<=g&&pr[j]<=n/i;++j)
        {
            p[i*pr[j]]=1;
            if (!(i%pr[j])) break;
        }
    }
    for (J=0;pr[J+1]<=X;++J);
    for (i=1;i<=J;an+=D[i],++i)
        for (D[i]=pr[i];D[i]*pr[i]<=n;D[i]*=pr[i]);
    for (;i<=g;++i) an+=pr[i];

    s=g+1,e=s+1,k=1;
    for (i=1;i<=J;++i) jb(s,i,1,0);
    for (;i<=g;++i) jb(i,e,1,0);
    int d;
    for (j=J+1;j<=g;++j)
        for (i=1;i<=J;++i)
        {
            z=n/pr[j];
            for (d=1;d*pr[i]<=z;d*=pr[i]);
            if (d*pr[j]>D[i]+pr[j])
                jb(i,j,1,d*pr[j]-D[i]-pr[j]);
        }
    while (SPFA()) addflow();
    printf("%lld\n",an+1);
    return 0;
}