Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int MAXN = 100000 + 1;
- typedef long long ll;
- struct tree{
- size_t vertex_cnt = 0;
- size_t D = 0;
- size_t maxR = 0;
- size_t minR = -1;
- size_t dR;
- size_t *R = nullptr;
- size_t *Rcnt = nullptr;
- size_t *sRcnt = nullptr;
- ll *Rtot = nullptr;
- ll *sRtot = nullptr;
- };
- struct vertex {
- size_t degree;
- size_t radius = 0;
- vertex **edges = nullptr;
- tree *component = nullptr;
- };
- typedef tree* forest;
- typedef vertex* branch;
- typedef size_t* size_t_ptr;
- typedef ll* ll_t_ptr;
- vertex *vertex_list;
- void nullify_edges(vertex *leaf){
- assert(leaf);
- for (size_t i = 0; i < leaf->degree; ++i){
- leaf->edges[i] = nullptr;
- }
- }
- void set_degree(vertex *leaf, size_t degree){
- assert(leaf);
- leaf->degree = degree;
- leaf->edges = new branch[degree];
- nullify_edges(leaf);
- }
- void make_edge(vertex *a, size_t &a_cur_deg, vertex *b, size_t &b_cur_deg){
- assert(a);
- assert(b);
- assert(a_cur_deg != a->degree && b_cur_deg != b->degree);
- a->edges[a_cur_deg++] = b;
- b->edges[b_cur_deg++] = a;
- }
- void union_dfs(size_t &vertex_cnt, vertex *cur, vertex *prev = nullptr){
- ++vertex_cnt;
- for (size_t i = 0; i < cur->degree; ++i){
- vertex *next = cur->edges[i];
- if (next == prev){
- continue;
- }
- next->component = cur->component;
- union_dfs(vertex_cnt, next, cur);
- }
- }
- vertex* calc_dfs(vertex *cur, vertex *prev = nullptr, size_t radius = 0){
- cur->radius = max(cur->radius, radius);
- vertex *best = nullptr;
- for (size_t i = 0; i < cur->degree; ++i){
- vertex *next = cur->edges[i];
- if (next == prev){
- continue;
- }
- vertex *next_best = calc_dfs(next, cur, radius + 1);
- if (!best || next_best->radius > best->radius){
- best = next_best;
- }
- }
- if (best){
- return best;
- } else {
- return cur;
- }
- }
- void Rset_dfs(tree &seed, size_t &Rit, vertex *cur, vertex *prev = nullptr){
- assert(Rit != seed.vertex_cnt);
- seed.R[Rit++] = cur->radius;
- seed.maxR = max(seed.maxR, cur->radius);
- seed.minR = min(seed.minR, cur->radius);
- for (size_t i = 0; i < cur->degree; ++i){
- vertex *next = cur->edges[i];
- if (next == prev){
- continue;
- }
- Rset_dfs(seed, Rit, next, cur);
- }
- }
- void make_tree(vertex *leaf){
- tree *seed = new tree;
- size_t &vertex_cnt = seed->vertex_cnt,
- &D = seed->D,
- &minR = seed->minR,
- &maxR = seed->maxR,
- &dR = seed->dR;
- size_t_ptr &R = seed->R,
- &Rcnt = seed->Rcnt,
- &sRcnt = seed->sRcnt;
- ll_t_ptr &Rtot = seed->Rtot,
- &sRtot = seed->sRtot;
- leaf->component = seed;
- union_dfs(vertex_cnt, leaf);
- calc_dfs(calc_dfs(calc_dfs(leaf)));
- R = new size_t[vertex_cnt];
- size_t Rit = 0;
- Rset_dfs(*seed, Rit, leaf);
- D = maxR;
- dR = maxR - minR;
- sort(R, R + vertex_cnt);
- Rcnt = new size_t[dR + 1];
- sRcnt = new size_t[dR + 1];
- size_t str = 1, it = 0;
- for (size_t i = 1; i < vertex_cnt; ++i){
- if (R[i] == R[i - 1]){
- ++str;
- } else {
- Rcnt[it] = str;
- sRcnt[it] = it ? sRcnt[it - 1] + str : str;
- ++it;
- str = 1;
- }
- }
- Rcnt[it] = str;
- sRcnt[it] = it ? sRcnt[it - 1] + str : str;
- Rtot = new ll[dR + 1];
- sRtot = new ll[dR + 1];
- for (size_t i = 0; i <= dR; ++i){
- Rtot[i] = ll(minR + i) * ll(Rcnt[i]);
- sRtot[i] = i ? sRtot[i - 1] + Rtot[i] : Rtot[i];
- }
- }
- void make_forest(size_t vcnt, size_t ecnt, size_t *from, size_t *to){
- vertex_list = new vertex[vcnt];
- size_t degree[vcnt];
- for (size_t i = 0; i < vcnt; ++i){
- degree[i] = 0;
- }
- for (size_t i = 0; i < ecnt; ++i){
- ++degree[--from[i]];
- ++degree[--to[i]];
- }
- for (size_t i = 0; i < vcnt; ++i){
- set_degree(vertex_list + i, degree[i]);
- degree[i] = 0;
- }
- for (size_t i = 0; i < ecnt; ++i){
- make_edge(vertex_list + from[i], degree[from[i]], vertex_list + to[i], degree[to[i]]);
- }
- for (size_t i = 0; i < vcnt; ++i){
- if (!vertex_list[i].component){
- make_tree(vertex_list + i);
- }
- }
- }
- typedef long double ld;
- map < pair < tree*, tree* >, ld > cash;
- void calcD(size_t x, size_t y){
- tree *a = vertex_list[--x].component,
- *b = vertex_list[--y].component;
- if (a == b){
- puts("-1");
- return;
- }
- pair < tree*, tree* > pos = make_pair(a, b);
- if (cash.count(pos)){
- printf("%.10f\n", double(cash[pos]));
- return;
- }
- ll tot = ll(a->vertex_cnt) * ll(b->vertex_cnt);
- size_t limD = max(a->D, b->D);
- ll result = (ll(a->sRtot[a->dR]) * ll(b->sRcnt[b->dR]))
- + (ll(a->sRcnt[a->dR]) * ll(b->sRtot[b->dR]))
- + (ll(a->sRcnt[a->dR]) * ll(b->sRcnt[b->dR]));
- int scnt = limD - a->minR - b->minR;
- if (scnt < 1){
- printf("%.10f\n", double(cash[pos] = (result / ld(tot))));
- return;
- }
- if (a->dR > b->dR){
- swap(a, b);
- }
- size_t lim = min(a->dR + 1, size_t(scnt - 1));
- for (int i = 1; i <= lim; ++i){
- int x = i - 1,
- y = scnt - i - 1;
- if (b->dR < y){
- continue;
- }
- result -= (ll(a->Rcnt[x]) * b->sRtot[y] + a->Rtot[x] * ll(b->sRcnt[y]) + ll(a->Rcnt[x]) * ll(b->sRcnt[y]));
- result += (ll(a->Rcnt[x]) * ll(b->sRcnt[y]) * ll(limD));
- }
- printf("%.10f\n", double(cash[pos] = (result / ld(tot))));
- }
- int main(){
- size_t n, m, q;
- cin >> n >> m >> q;
- size_t *from = new size_t[m],
- *to = new size_t[m];
- for (size_t i = 0; i < m; ++i){
- cin >> from[i] >> to[i];
- }
- make_forest(n, m, from, to);
- for (size_t i = 0; i < q; ++i){
- size_t a, b;
- cin >> a >> b;
- calcD(a, b);
- }
- }
Add Comment
Please, Sign In to add comment