NormalFrom WJMZBMR
描述 Description

某天WJMZBMR学习了一个神奇的算法:树的点分治!
这个算法的核心是这样的:
消耗时间=0
Solve(树 a)
消耗时间 += a 的 大小
如果 a 中 只有 1 个点
退出
否则在a中选一个点x,在a中删除点x
那么a变成了几个小一点的树,对每个小树递归调用Solve
我们注意到的这个算法的时间复杂度跟选择的点x是密切相关的。
如果x是树的重心,那么时间复杂度就是O(nlogn)
但是由于WJMZBMR比较傻逼,他决定随机在a中选择一个点作为x!
Sevenkplus告诉他这样做的最坏复杂度是O(n^2)
但是WJMZBMR就是不信>_<。。。
于是Sevenkplus花了几分钟写了一个程序证明了这一点。。。你也试试看吧^_^
现在给你一颗树,你能告诉WJMZBMR他的傻逼算法需要的期望消耗时间吗?(消耗时间按在Solve里面的那个为标准)
输入格式 InputFormat
第一行一个整数n,表示树的大小
接下来n-1行每行两个数a,b,表示a和b之间有一条边
注意点是从0开始标号的
输出格式 OutputFormat
一行一个浮点数表示答案
四舍五入到小数点后4位
如果害怕精度跪建议用long double或者extended
样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint
其实跟点分治没什么大关系呢。。。真的吗?


这题就是求随机化点分治的期望复杂度啦。。

考虑点u和点v

u在Solve(v)有贡献当且仅当v是u到v中(包括uv)第一个被删掉的。

于是这题其实就是求

然后可以用点分治。合并子树的时候暴力是的。不过这题暴力也可以过,比较慢就是了(据说这是clj出的noip模拟赛。。。),快一点的话可以用FFT优化。

代码(由于bzoj挂了,所以就只在tyvj上交了):

#include <cstdio>
#include <algorithm>
#include <complex>
#include <cmath>
using std::complex;
const int N = 300005 * 2;
typedef complex<double> cp;
const double PI = acos(-1);
long double ans;
bool isrt[N];
int n,ec,son[N],lnk[N * 2],nxt[N * 2],sz[N];
inline bool cmp(int lhs,int rhs)
{
    return sz[lhs] < sz[rhs];
}
int bit_rev(int x,int n)
{
    int res = 0;
    for (int i = 0; i < n; ++i)
        res |= (x >> i & 1) << (n - i - 1);
    return res;
}
void fft(cp *a,int n,int rev)
{
    static cp y[N];
    int len = 1 << n;
    for (int i = 0; i < len; ++i) y[i] = a[bit_rev(i,n)];
    double Pi = PI * rev;
    for (int d = 1; d < len; d <<= 1) {
        cp x = exp(cp(0,Pi / d));
        for (int k = 0; k < len; k += (d << 1)) {
            cp w(1,0);
            for (int j = 0; j < d; ++j,w *= x) {
                cp u = y[k + j],v = w * y[k + j + d];
                y[k + j] = u + v;
                y[k + j + d] = u - v;
            }
        }
    }
    if (rev == -1)
        for (int i = 0; i < len; ++i) y[i] /= len;
    for (int i = 0; i < len; ++i) a[i] = y[i];
}
void mul(int *a,int *b,int m,int *c,int &lc)
{
    static cp t1[N],t2[N];
    int len = 1,n = 0;
    for (; len < 2 * m; len <<= 1) ++n;
    for (int i = 0; i < m; ++i) t1[i] = cp(a[i],0),t2[i] = cp(b[i],0);
    for (int i = m; i < len; ++i) t1[i] = cp(0,0),t2[i] = cp(0,0);
    fft(t1,n,1); fft(t2,n,1);
    for (int i = 0; i < len; ++i) t1[i] *= t2[i];
    fft(t1,n,-1);
    lc = len;
    for (int i = 0; i < len; ++i) c[i] = (int)(t1[i].real() + 0.5);
}
void work(int s)
{
    static int q[N],fa[N],d[N],to[N];
    static int Time,Time1,a[2][N],b[2][N],c[N];
    ++Time;
    int h = 1,t = 0;
    fa[s] = 0; d[s] = 0;
    for (q[++t] = s; h <= t; ++h) {
        sz[q[h]] = 0;
        for (int i = son[q[h]]; i; i = nxt[i])
            if (lnk[i] != fa[q[h]] && !isrt[lnk[i]]) {
                q[++t] = lnk[i];
                d[lnk[i]] = d[q[h]] + 1;
                fa[lnk[i]] = q[h];
            }
    }
    for (int i = t; i > 1; --i) sz[fa[q[i]]] += ++sz[q[i]];
    to[0] = 0;
    for (int i = son[s]; i; i = nxt[i])
        if (!isrt[lnk[i]]) to[++to[0]] = lnk[i];
    std::sort(to + 1,to + 1 + to[0],cmp);
    for (int k = 1; k <= to[0]; ++k) {
        ++Time1;
        q[h = t = 1] = to[k];
        for (int u; h <= t; ++h) {
            if (b[0][d[u = q[h]]] != Time1) b[0][d[u]] = Time1,b[1][d[u]] = 0;
            ++b[1][d[u]];
            for (int i = son[u]; i; i = nxt[i])
                if (lnk[i] != fa[u] && !isrt[lnk[i]]) q[++t] = lnk[i];
        }
        int len = 0;
        for (int i = 1; i <= sz[to[k]] + 1; ++i) {
            if (a[0][i] != Time) a[0][i] = Time,a[1][i] = 0;
            if (b[0][i] != Time1) b[0][i] = Time1,b[1][i] = 0;
        }
        for (int i = 1; i <= sz[to[k]]; ++i)
            ans += 1.0 * b[1][i] / (i + 1);
        mul(a[1],b[1],sz[to[k]] + 2,c,len);
        // for (int j = 1; j <= m; ++j)
     //     for (int i = 1; i <= m; ++i)
     //         if (a[0][j] == Time) ans += 1.0 * b[1][i] * a[1][j] / (j + i);
     for (int i = 1; i < len; ++i)
            ans += 1.0 * c[i] / i;
        for (int i = 1; i <= sz[to[k]]; ++i)
            a[1][i + 1] += b[1][i];
    }
}
int fc(int s)
{
    //isrt[s] = true;return s;
 static int q[N],f[N],g[N],fa[N];
    int h = 1,t = 0,res = 0;
    g[0] = 0x3f3f3f3f;
    fa[s] = 0;
    for (q[++t] = s; h <= t; ++h) {
        f[q[h]] = g[q[h]] = 0;
        for (int i = son[q[h]]; i; i = nxt[i])
            if (lnk[i] != fa[q[h]] && !isrt[lnk[i]]) {
                q[++t] = lnk[i];
                fa[lnk[i]] = q[h];
            }
    }
    for (int i = t; i; --i) {
        f[fa[q[i]]] += ++f[q[i]];
        g[fa[q[i]]] = std::max(g[fa[q[i]]],f[q[i]]);
        g[q[i]] = std::max(g[q[i]],t - f[q[i]]);
        if (g[res] > g[q[i]]) res = q[i];
    }
    isrt[res] = true;
    return res;
}
void solve(int s)
{
    static int q[N];
    int h = 1,t = 0;
    for (q[++t] = fc(s); h <= t; ++h) {
        work(q[h]);
        for (int i = son[q[h]]; i; i = nxt[i])
            if (!isrt[lnk[i]]) q[++t] = fc(lnk[i]);
    }
}
inline void addedge(int x,int y)
{
    nxt[++ec] = son[x];
    son[x] = ec;
    lnk[ec] = y;
}
int main()
{
    scanf("%d",&n);
    for (int i = 1,x,y; i < n; ++i) {
        scanf("%d%d",&x,&y);
        ++x; ++y;
        addedge(x,y); addedge(y,x);
    }
    solve(1);
    printf("%.4f\n",(double)ans * 2 + n);
}

Comments

comments powered by Disqus
Copyright © 2013 lazycal of Shen Ben
Powered by Logdown and Greyshade
Favicon from The Noun Project