Luogu

分析

看到这个巨大的误差允许范围，可以考虑乱搞。

我们给所有入度为 $0$ 的点赋一个随机权值，然后将每个点的权值设为所有能到达这个点的点权的最小值。

经过一番推导后可以发现，这个权值的期望是 $\frac{\mathrm{RAND\_MAX}}{k}$，这里的 $k$ 是能到达这个点的入度为$0$的点的个数。那么这样子就能够估算出 $k$ 了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define min(a,b) (((a)<(b))?(a):(b))
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int T=100;
const int N=1000000+10;

int x[N],y[N],w[N];
double ans[N];

int main() {
    srand(19260817);
    int n=read(),m=read();
    for (re int i=m+1;i<=n;++i) x[i]=read(),y[i]=read();
    for (re int t=1;t<=T;++t) {
        for (re int i=1;i<=m;++i) w[i]=rand();
        for (re int i=m+1;i<=n;++i) {
            w[i]=min(w[x[i]],w[y[i]]);
            ans[i]+=w[i];
        }
    }
    for (re int i=m+1;i<=n;++i)
        printf("%d\n",(int)(RAND_MAX/ans[i]*T-0.5));
    return 0;
}