1. 题目

传送门=￣ω￣=

题意：给你一颗树，问你有多少条路径长度为素数。

点数 $\leq 50000$

2. 题解

emmmm…

路径条数显然点分治

然后对于每个点 $p$弄个向量，向量的维度是 $p$的子树大小，向量的第 $i$维的值等于 $p$的子树中到 $p$的深度为 $i$的点的数目。设该向量为 $a$

那么拿 $a$自乘一波，得到的向量 $a^2$的第 $i$维的值就是经过 $p$的长度为 $i$的路径条数了。

但是这样子可能会出现某路径两端均在 $p$的某个儿子的子树内，这种情况是不合法的，需要减掉。那么对于 $p$的某个儿子节点 $x$设向量 $b$，$b$的第 $i$维表示 $x$的子树中到 $p$的深度为 $i$的点的数目，拿 $b$自乘得到 $b^2$，那么 $b^2$就是不合法的方案数了，减掉即可。

至于所谓的素数，暴力 $O(n\sqrt n)$找素数即可。

代码：

#include <bits/stdc++.h>

#define NS (50005)
#define PI (3.14159265358979323846)

using namespace std;

typedef complex<double> cpx;
typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct graph
{
    int head[NS], nxt[NS << 1], to[NS << 1], sz;
    void init() {memset(head, -1, sizeof(head)), sz = 0;}
    graph() {init();}
    void push(int a, int b)
    {
        nxt[sz] = head[a], to[sz] = b, head[a] = sz++;
    }
    int operator [] (const int a) const {return to[a];}
} g;

int n, rev[NS * 3];

LL num[NS * 3];

int root, rmx, sz[NS], sum, dep[NS];

bool book[NS];

cpx poly[NS * 3];

void Get_Rev(int N, int bs)
{
    for (int i = 1; i < N; i += 1)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bs - 1));
}

void DFT(cpx* a, int N, int f)
{
    for (int i = 0; i < N; i += 1) if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int l = 1; l < N; l <<= 1)
    {
        cpx w1(cos(PI / l), sin(PI / l) * f);
        for (int i = 0; i < N; i += (l << 1))
        {
            cpx w(1, 0), t1, t2;
            for (int j = i; j < i + l; j += 1, w *= w1)
                t1 = a[j], t2 = w * a[j + l], a[j] = t1 + t2, a[j + l] = t1 - t2;
        }
    }
    if (f == -1) for (int i = 0; i < N; i += 1) a[i] /= N;
}

void SzDfs(int a, int fa)
{
    sz[a] = 1;
    for (int i = g.head[a]; ~i; i = g.nxt[i])
        if (g[i] != fa && !book[g[i]])
            SzDfs(g[i], a), sz[a] += sz[g[i]];
}

void GetRoot(int a, int fa)
{
    int mx = sum - sz[a];
    for (int i = g.head[a]; ~i; i = g.nxt[i])
        if (g[i] != fa && !book[g[i]])
            mx = max(mx, sz[g[i]]), GetRoot(g[i], a);
    if (mx < rmx) rmx = mx, root = a;
}

void DepDfs(int a, int fa)
{
    dep[a] = dep[fa] + 1;;
    poly[dep[a]].real(poly[dep[a]].real() + 1);
    for (int i = g.head[a]; ~i; i = g.nxt[i])
        if (!book[g[i]] && g[i] != fa)
            DepDfs(g[i], a);
}

void Binary()
{
    int a = root; book[a] = 1;
    int N = 1, bs = 0;
    while (N < (sum << 1)) N <<= 1, bs++;
    for (int i = 0; i < N; i += 1) poly[i] = cpx(0, 0);
    Get_Rev(N, bs), DepDfs(a, 0), DFT(poly, N, 1);
    for (int i = 0; i < N; i += 1) poly[i] *= poly[i];
    DFT(poly, N, -1);
    for (int i = 0; i < N; i += 1) num[i] += (LL)(poly[i].real() + 0.5);
    SzDfs(a, 0);
    for (int i = g.head[a]; ~i; i = g.nxt[i])
        if (!book[g[i]])
        {
            N = 1, bs = 0;
            while (N <= (sz[g[i]] << 1)) N <<= 1, bs++;
            for (int i = 0; i < N; i += 1) poly[i] = cpx(0, 0);
            Get_Rev(N, bs), DepDfs(g[i], a);
            DFT(poly, N, 1);
            for (int i = 0; i < N; i += 1) poly[i] *= poly[i];
            DFT(poly, N, -1);
            for (int i = 0; i < N; i += 1) num[i] -= (LL)(poly[i].real() + 0.5);
        }
    for (int i = g.head[a]; ~i; i = g.nxt[i])
        if (!book[g[i]])
            sum = sz[g[i]], rmx = INT_MAX, GetRoot(g[i], a), Binary();
}

bool Jud(int a)
{
    for (int i = 2; i * i <= a; i += 1)
        if (a % i == 0) return 0;
    return 1;
}

int main(int argc, char const* argv[])
{
    IN(n), dep[0] = -1;
    for (int i = 1, a, b; i < n; i += 1)
        IN(a), IN(b), g.push(a, b), g.push(b, a);   
    SzDfs(1, 0), sum = sz[1], rmx = INT_MAX, GetRoot(1, 0);
    Binary(); double ans = 0;
    for (int i = 2; i <= n; i += 1)
        if (Jud(i)) ans += num[i] >> 1;
    printf("%.7f\n", ans / (0.5 * n * (n - 1)));
    return 0;
}