No Abstracts.

Des.

Calculate the expectation of time complexity of Divide and Conquer when randomly choosing a center of a subtree.

Sol.

Enumerate the center and the son and calculate the expectation, as $P(i,j) \times 1$ for $j$ is in $i$\’s subtree(in D&C structure). Sum up all $E(i,j)$ is correct.

Convert the problem model again, $j$ is in $i$\’s subtree means that we first chosen $i$ then chosen $j$ ignoring other nodes on that chain between the 2 nodes. So the probability is $\frac{1}{dis(i,j)}$, notice that $P(i,i)$ is 1.

Thus we should calculate the total number of paths of each length, using FFT to boost the process. The time complexity is $O(n \log^2n)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <bits/stdc++.h>

using namespace std;

const int maxn = 30005;
const int maxp = 270005;
const double PI = acos(-1.0);

struct comp {
  double r, i;
  comp(double r_ = 0.0, double i_ = 0.0) : r(r_), i(i_) {}
  inline comp operator+(comp rhs) {
    return comp(r + rhs.r, i + rhs.i);
  }
  inline comp operator-(comp rhs) {
    return comp(r - rhs.r, i - rhs.i);
  }
  inline comp operator*(comp rhs) {
    return comp(r * rhs.r - i * rhs.i, r * rhs.i + i * rhs.r);
  }
  inline comp conj() {
    return comp(r, -i);
  }
}omega[maxp], _omega[maxp], A[maxp];
struct edge {
  int to, nxt;
}e[maxn << 1];
int n, ptr, lnk[maxn], vis[maxn], mx[maxn];
int siz[maxn], sum, glbmn, rt;
int d[maxn], tot;
int rev[maxp];
int bkt[maxn << 2];

inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}
inline void add(int bgn, int end) {
  e[++ptr] = (edge){end, lnk[bgn]};
  lnk[bgn] = ptr;
}
inline void FFT(comp *a, int N, int L, int typ) {
  for (int i = 0; i < N; ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (L - 1));
  double round = 2.0 * PI / N;
  for (int i = 0; i < N; ++i) {
    if (typ == 1) {
      omega[i] = comp(cos(i * round), sin(i * round));
    } else {
      _omega[i] = comp(cos(i * round), -1.0 * sin(i * round));
    }
  }
  comp *w = NULL;
  if (typ == 1) w = omega;
  else w = _omega;
  for (int i = 0; i < N; ++i)
    if (i > rev[i]) swap(a[i], a[rev[i]]);
  for (int i = 2; i <= N; i <<= 1) {
    int m = (i >> 1);
    for (int j = 0; j < N; j += i) {
      for (int k = 0; k < m; ++k) {
        comp t = a[j + m + k] * w[N / i * k];
        a[j + m + k] = a[j + k] - t;
        a[j + k] = a[j + k] + t;
      }      
    }
  }
  if (typ == -1) {
    for (int i = 0; i < N; ++i)
      a[i].r /= N;
  }
}
void getroot(int x, int fa) {
  siz[x] = 1;
  mx[x] = 0;
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (y == fa || vis[y]) continue;
    getroot(y, x);
    siz[x] += siz[y];
    mx[x] = max(mx[x], siz[y]);
  }
  mx[x] = max(mx[x], sum - siz[x]);
  if (mx[x] < glbmn) 
    glbmn = mx[x], rt = x;
}
void getdep(int x, int fa, int dep) {
  d[++tot] = dep;
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (y == fa || vis[y]) continue;
    getdep(y, x, dep + 1);
  }
}
void calc(int x, int dep, int tg) {
  tot = 0;
  getdep(x, 0, dep);
  int mxv = 0;
  for (int i = 1; i <= tot; ++i)
    mxv = max(mxv, d[i]);
  int N = 1, L = 0;
  while (N <= 2 * mxv) N <<= 1, L++;
  for (int i = 0; i < N; ++i) A[i].r = A[i].i = 0;
  for (int i = 1; i <= tot; ++i) A[d[i]].r++;
  FFT(A, N, L, 1);
  for (int i = 0; i < N; ++i) A[i] = A[i] * A[i];
  FFT(A, N, L, -1);
  for (int i = 0; i <= 2 * mxv; ++i) {
    if (tg) bkt[i] -= (int)(A[i].r + 0.5);
    else bkt[i] += (int)(A[i].r + 0.5);
  }
}
void solve(int x) {
  vis[x] = 1;
  calc(x, 0, 0);
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (vis[y]) continue;
    calc(y, 1, 1);
    glbmn = 0x3f3f3f3f;
    rt = 0;
    sum = siz[y];
    getroot(y, 0);
    solve(rt);
  }
}

int main() {
  n = rd();
  int u, v;
  for (int i = 1; i < n; ++i) {
    u = rd(); v = rd();
    ++u; ++v;
    add(u, v); 
    add(v, u);
  }
  glbmn = 0x3f3f3f3f; rt = 0;
  sum = n;
  getroot(1, 0);
  solve(rt);
  long double ans = 0.0;
  for (int i = 0; i < n; ++i) {
    ans += (long double)bkt[i] / (i + 1);
  }
  printf("%.4Lf\n", ans);
  return 0;
}