Sol：点分治，每次递归处理时，假设当前的重心是\(root\)，求出分裂后的子树的所有点到\(root\)的距离，并统计它们的个数。
记\(cnt[d]\)为距离为\(d\)的路径的个数。同时还要求出所有距离相加的个数，因为这些距离是可以组合的，这一步可以利用\(NTT\)快速求出。
多项式形式为\(\sum cnt[d]x^d\)，求完后暴力统计所有长度为素数的边的个数。算完后统计答案由于\(u\)到\(v\)和\(v\)到\(u\)会统计两遍，所以答案还要除以2。分治到子树时，由于答案会可能会算重，因为在统计\(root\)的子树时可能会算到在同一个子树内的两点，所以在统计子树时要先利用容斥原理减去算重的，然后再分治算子树。
代码还有问题，不过大概思路就是这样，先插个眼
#include <bits/stdc++.h> #define ll long long #define pb push_back using namespace std; const int N = 5e6+10; const int p = 998244353, gg = 3, ig = 332738118, img = 86583718;//1004535809 const int mod=998244353; template <typename T> void rd (T &x) { x=0;int f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();} while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar(); x*=f; } ll qpow(ll a, int b) { ll res = 1; while(b) { if(b & 1) res = 1ll * res * a % mod; a = 1ll * a * a % mod; b >>= 1; } return res; } vector<ll>A(N); namespace Poly { #define mul(x, y) (1ll * x * y >= mod ? 1ll * x * y % mod : 1ll * x * y) #define minus(x, y) (1ll * x - y < 0 ? 1ll * x - y + mod : 1ll * x - y) #define plus(x, y) (1ll * x + y >= mod ? 1ll * x + y - mod : 1ll * x + y) #define ck(x) (x >= mod ? x - mod : x)//取模运算太慢了 typedef vector<ll> poly; const int G = 3;//根据具体的模数而定，原根可不一定不一样！！！ //一般模数的原根为 2 3 5 7 10 6 const int inv_G = qpow(G, mod - 2); int RR[N], deer[2][21][N], inv[N]; void init(const int t) {//预处理出来NTT里需要的w和wn，砍掉了一个log的时间 for(int p = 1; p <= t; ++ p) { int buf1 = qpow(G, (mod - 1) / (1 << p)); int buf0 = qpow(inv_G, (mod - 1) / (1 << p)); deer[0][p][0] = deer[1][p][0] = 1; for(int i = 1; i < (1 << p); ++ i) { deer[0][p][i] = 1ll * deer[0][p][i - 1] * buf0 % mod;//逆 deer[1][p][i] = 1ll * deer[1][p][i - 1] * buf1 % mod; } } inv[1] = 1; for(int i = 2; i <= (1 << t); ++ i) inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod; } int NTT_init(int n) {//快速数论变换预处理 int limit = 1, L = 0; while(limit < n) limit <<= 1, L ++ ; for(int i = 0; i < limit; ++ i) RR[i] = (RR[i >> 1] >> 1) | ((i & 1) << (L - 1)); return limit; } void NTT(poly &A, int type, int limit) {//快速数论变换 A.resize(limit); for(int i = 0; i < limit; ++ i) if(i < RR[i]) swap(A[i], A[RR[i]]); for(int mid = 2, j = 1; mid <= limit; mid <<= 1, ++ j) { int len = mid >> 1; for(int pos = 0; pos < limit; pos += mid) { int *wn = deer[type][j]; for(int i = pos; i < pos + len; ++ i, ++ wn) { int tmp = 1ll * (*wn) * A[i + len] % mod; A[i + len] = ck(A[i] - tmp + mod); A[i] = ck(A[i] + tmp); } } } if(type == 0) { for(int i = 0; i < limit; ++ i) A[i] = 1ll * A[i] * inv[limit] % mod; } } inline poly poly_mul(poly A, poly B) {//多项式乘法 int deg = A.size() + B.size() - 1; int limit = NTT_init(deg); poly C(limit); NTT(A, 1, limit); NTT(B, 1, limit); for(int i = 0; i < limit; ++ i) C[i] = 1ll * A[i] * B[i] % mod; NTT(C, 0, limit); C.resize(deg); return C; } //多个多项式相乘CDQ或者利用优先队列启发式合并 inline poly CDQ(int l,int r) { if(l==r) { return poly{1,A[l]}; } int mid=l+r>>1; poly L=CDQ(l,mid); poly R=CDQ(mid+1,r); return poly_mul(L,R); } } using namespace Poly; constexpr int MAXN=5e4+10; vector<int>E[MAXN]; int mxson[MAXN],sz[MAXN]; int n,S,MX,root; bool vis[MAXN],st[MAXN]; int primes[MAXN],primes_cnt; void get_primes() { for(int i=2;i<=50000;i++) { if(!st[i]) primes[++primes_cnt]=i; for(int j=1;primes[j]*i<=50000;i++) { st[primes[j]*i]=1; if(i%primes[j]==0) break; } } } void getroot(int u,int fa) { sz[u]=1,mxson[u]=0; for(auto &v:E[u]) { if(v==fa||vis[v]) continue; getroot(v,u); sz[u]=sz[u]+sz[v]; mxson[u]=max(mxson[u],sz[v]); } mxson[u]=max(mxson[u],S-sz[u]); if(mxson[u]<MX) root=u,MX=mxson[u]; } int cnt[MAXN],Len; ll res=0; void getdist(int u,int fa,int d) { ++cnt[d]; Len=max(Len,d); for(auto &v:E[u]) { if(vis[v]||v==fa) continue; getdist(v,u,d+1); } } void solve(int u,int d,int type) { Len=0; ll sum=0; getdist(u,0,d); poly F(Len+1); for(int i=0;i<=Len;i++) F[i]=cnt[i]; sum-=cnt[1]; poly G=poly_mul(F,F); int limit=G.size(); for(int i=1;i<=primes_cnt;i++) if(primes[i]>limit) break; else sum+=G[primes[i]]; res+=sum/2*type; for(int i=0;i<=Len;i++) cnt[i]=0; } void Divide(int u) { solve(u,0,1); vis[u]=1; for(auto &v:E[u]) { if(vis[v]) continue; solve(v,1,-1); S=sz[v],root=0,MX=MAXN; getroot(v,0); Divide(v); } } int main() { //freopen("in.in","r",stdin); //ios::sync_with_stdio(false); //cin.tie(nullptr); get_primes(); init(20);//2^21 = 2,097,152,根据题目数据多项式项数的大小自由调整，注意大小需要跟deer数组同步(21+1=22) rd(n); for(int i=1;i<n;i++) { int u,v; rd(u),rd(v); E[u].emplace_back(v); E[v].emplace_back(u); } S=n,MX=MAXN,root=0; getroot(1,0); Divide(root); printf("%.1lf\n",res*2.0/(1.0*n*(n-1))); return 0; } 2.Constructing Ranches$ (2019-ICPC-HongKong)题意：给定一棵\(n\)个点的树，每个点有一个点权，问有多少条路径满足路径上的点权可以构成一个简单的凸多边形。