洛谷题目传送门

萝卜大毒瘤

题意可以简化成这样：给一个DAG，求每个点能够从多少个入度为\(0\)的点到达（记为\(k\)）。

一个随机做法：给每个入度为\(0\)的点随机一个权值，在DAG上求出每个点能够返回到的入度为\(0\)的点的最小权值，那么这个权值的期望是\(\frac{\text{随机值域}}{k+1}\)。多选几套随机权值（蒟蒻选了一百次），跑出来的平均值即可输出。

实在是太玄学了。

#include<bits/stdc++.h>

#define LL unsigned long long

#define RG register

#define R RG int

#define G if(++ip==ie)if(fread(ip=buf,1,SZ,stdin))

#define F(S) if(freopen(S".in","r",stdin));if(freopen(S".out","w",stdout))

using namespace std;

const int SZ=1<<18,N=1e6+1,S=50,T=2;

char buf[SZ],*ie=buf+SZ,*ip=ie-1;

inline int in(){

    G;while(*ip<'-')G;

    R x=*ip&15;G;

    while(*ip>'-'){x*=10;x+=*ip&15;G;}

    return x;

}

inline int Min(R x,R y){

    return x<y?x:y;

}

int f[N][S],c[N][2];

double ans[N];

int main(){

    srand(20020307);

    R n=in(),m=in();

    for(R i=m+1;i<=n;++i)

        c[i][0]=in(),c[i][1]=in();

    for(R t=T;t;--t){

        for(R i=1;i<=m;++i)

            for(R j=0;j<S;++j)

                f[i][j]=rand();

        for(R i=m+1;i<=n;++i)

            for(R j=0;j<S;++j)

                ans[i]+=f[i][j]=Min(f[c[i][0]][j],f[c[i][1]][j]);

    }

    for(R i=m+1;i<=n;++i)

        printf("%d\n",(int)(RAND_MAX/ans[i]*S*T-0.5));

    return 0;

}