Codeforces Round #343 (Div. 2) E. Famil Door and Roads

题目链接：

http://www.codeforces.com/contest/629/problem/E

题解：

树形dp。

siz[x]为x这颗子树的节点个数（包括x自己）

dep[x]表示x这个节点的深度，从1开始（其实从什么开始都可以，我们这里用到的只是相对距离）

对于查询u，v，总共有三种情况：

1、u为公共祖先

设x为(u,v)链上u的儿子，则我们知道新边只能从非x子树的点(n-siz[x]连到以v为根的子树上的点(siz[v])

则新边的总条数为(n-siz[x])*siz[v]

现在用树形dp（跑两趟，树形dp的常见用法）可以求出u到(n-siz[x])这些点的距离的和(sd1)，以及v到siz[v]这些点的距离的和(sd2)

且(u,v)这条链的长度为Len=dep[u]+dep[v]-2*dep[Lca(u,v)]；

组合数学一下，那么答案就是:ans=(sd1*siz[v]+sd2*(n-siz[x])+(n-siz[x])*siz[v]+Len*(n-siz[x])*siz[v])/((n-siz[x])*siz[v])

2、v为公共祖先

同上

3、u,v都不是公共祖先

比上面的更一般化了，把对象(n-siz[x])变成siz[v]就可以了：

ans=(sd1*siz[v]+sd2*siz[u]+siz[u]*siz[v]+Len*siz[u]*siz[v])/(siz[u]*siz[v])

#pragma comment(linker, "/STACK:102400000,102400000") 
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

typedef long long LL;
const int maxn = 100000+10;
const int maxm = 22;

int n, m;

vector<int> G[maxn];

int siz[maxn], dep[maxn],lca[maxn][maxm];
LL sdown[maxn],sall[maxn];
void dfs(int u,int fa,int d) {
    dep[u] = d, siz[u] = 1, sdown[u] = 0;
    lca[u][0] = fa;
    for (int i = 1; i < maxm; i++) {
        int f = lca[u][i - 1];
        lca[u][i] = lca[f][i - 1];
    }
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == fa) continue;
        dfs(v, u, d + 1);
        siz[u] += siz[v];
        sdown[u] += siz[v] + sdown[v];
    }
}
void dfs2(int u, int fa) {
    if (fa == 0) sall[u] = sdown[u];
    else sall[u] = sall[fa] + n - 2 * siz[u];
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == fa) continue;
        dfs2(v, u);
    }
}

inline void up(int &u,int d){
    for (int i = maxm - 1; i >= 0; i--) {
        if (dep[lca[u][i]] >= d) u = lca[u][i];
    }
}

int Lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    up(u, dep[v]);
    if (u == v) return u;
    for (int i = maxm - 1; i >= 0; i--) {
        if (lca[u][i] != lca[v][i]) {
            u = lca[u][i];
            v = lca[v][i];
        }
    }
    return lca[u][0];
}

void query() {
    int u, v;
    scanf("%d%d", &u, &v);
    int anc = Lca(u, v);
    //(u,v)链上的边的贡献+新增的边的贡献
    double ans = dep[v] + dep[u] - 2 * dep[anc] + 1;
    if (anc == v) swap(u, v);
    if (anc == u) {
        //x为(u,v)链上u的儿子
        int x = v; up(x, dep[u] + 1);
        //除x所在子树的点外到所有点的距离的和
        LL tmp = sall[u] - sdown[x] - siz[x];
        //ans+=(tmp*siz[v]+sdown[v]*(n-siz[x]))/((n-siz[x])*siz[v])
        ans += 1.0*tmp / (n - siz[x]) + 1.0*sdown[v] / siz[v];
    }
    else {
        //ans+=(sdown[v]*siz[u]+sdown[u]*siz[v])/(siz[v]*siz[u])
        ans += 1.0*sdown[v] / siz[v] + 1.0*sdown[u] / siz[u];
    }
    printf("%.8lf
", ans);
}

void init() {
    for (int i = 1; i <= n; i++) G[i].clear();
}

int main() {
    while (scanf("%d%d", &n, &m) == 2 && n) {
        init();
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(1, 0, 1);
        dfs2(1, 0);
        while (m--) query();
    }
    return 0;
}