Description
富爷说来一棵树，于是大头栽了一棵树。树大了，有n个点和n - 1条边，任意两个点都是联通的，点的标号为1 - n。爱树的大头和富爷在树上安居乐业，但大头住在u，而富爷住在v,他们都很不高兴，因为u到v有且只有一条简单路径。 当然了，树王富爷找到了解决办法，他打算带着大头再给树建一条边（保证不是自环），而且他们会在n * (n - 1) / 2的方案中随机选择一种。 但，要让富爷和大头开心是有条件的。只有新建边之后，富爷去大头家以及大头去富爷家存在两条路径不会走相同的边时，他们才会呵呵（也就是说 存在一个简单环包含u和v）。 不开心的事情选择忘记。当富爷和大头开心时，你能得到愉快值等于环的大小。所以，你要告诉富爷和大头，当他们开心时（只考虑在环内），他们的期望愉悦值。
Input
第 1 行包含 2个正整数n 和 m (2≤n,m≤100000)，表示树有n 个点，以及有m组询问。 接下来n−1行描述了一些双联通边，每行包含两个整数ai和bi,(1≤ai,bi≤n)，表示第i条路连接的两个点。 最后m行描述富爷和大头，第i行包含两个整数ui和vi，(1≤ui,vi≤n,ui≠vi)，表示富爷和大头分别住在哪里。
Output
对于每组询问你需要输出如果富爷和大头开心的期望愉快度。你的答案与标准答案误差不能超过1e-6。
Sample Input
输入1： 4 3 2 4 4 1 3 2 3 1 2 3 4 1 输入2： 3 3 1 2 1 3 1 2 1 3 2 3
Sample Output
输出1： 4.00000000 3.00000000 3.00000000 输出2： 2.50000000 2.50000000 3.00000000 【输入输出样例 2 说明】 1、(1,2)和（2，3）均能让富爷和大头开心，则期望愉悦值为（2 + 3）/ 2 = 2.5 2、(1,3)和（2，3）均能让富爷和大头开心，则期望愉悦值为（2 + 3）/ 2 = 2.5 3、(2,3)能使富爷和大头开心，则期望愉悦值为3
Data Constraint
20% n,m <= 2000 40% n,m <= 10^5 树是随机的 60% n,m <= 10^5 每个点的度数均为2 100% n,m <= 10^5
分析
题意大概就是树上加一条边使一对点在一个简单环中的期望环长
我们发现，其实答案就是dist(u,v)*size[u]*size[v]+f[u]*size[v]+f[v]*size[u]
dist就是u到v的路径长度，size是子树大小，f是子树内所有点到子树的根的距离和
分母也显然是size[u]*size[v]
然后我们发现size和f都是可以预处理的，dist可以直接得出
然后如果u，v有祖孙关系的话，子树就不是往常意义的子树（假设v是祖先），那就是除了有u的那棵子树以外的都是v的子树
所以要处理一个g[v]来搞这种情况
#include#include #include #include using namespace std;typedef long long ll;const int N=1e5+10;struct Edge { int v,nx;}e[2*N];int cnt,list[N];int fa[N][20],dep[N];ll f[N],g[N],sz[N];int n,m,logn;void Add(int u,int v) { e[++cnt]=(Edge){v,list[u]};list[u]=cnt; e[++cnt]=(Edge){u,list[v]};list[v]=cnt;}void DFS(int u,int fat) { fa[u][0]=fat;dep[u]=dep[fat]+1;sz[u]=1; for (int i=list[u];i;i=e[i].nx) if (e[i].v!=fat) { DFS(e[i].v,u); sz[u]+=sz[e[i].v]; f[u]+=f[e[i].v]+sz[e[i].v]; }}void DFS_G(int u,int fa) { if (fa) g[u]=f[fa]-f[u]-sz[u]+g[fa]+(n-sz[fa]); for (int i=list[u];i;i=e[i].nx) if (e[i].v!=fa) DFS_G(e[i].v,u);}int LCA(int u,int v) { for (int i=logn;i>=0;i--) if (dep[fa[u][i]]>=dep[v]) u=fa[u][i]; if (u==v) return v; for (int i=logn;i>=0;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0];}int Witch_Son(int u,int v) { for (int i=logn;i>=0;i--) if (dep[fa[u][i]]>dep[v]) u=fa[u][i]; return u;}int main() { scanf("%d%d",&n,&m); for (int i=1,u,v;i