CF629E Famil Door and Roads

CF629E Famil Door and Roads

一、题目

点此看题

二、解法

关键在于讨论 l c a lca lca在哪儿，计算出了环的长度总和就有了环的平均长度：

• 如果不等于 u / v u/v u/v，那么统计出 u u u子树内所有点到他的距离和，统计出 v v v子树内所有点到它的距离和，两边长度贡献计算是独立的，于是可以用第一个值乘以 v v v子树点个数，第二个乘以 u u u子树点个数。
• 如果等于 u u u（ v v v同理），找到 u u u在 v v v方向的第一个儿子，一开始可以先统计每个点向上的距离和大小，然后就可以用类似第一种情况的方法算（不懂看看代码里怎么算的，有点复杂）

#include <cstdio>
#include <iostream>
using namespace std;
#define int long long
const int M = 100005;
int read()
{int x=0,flag=1;char c;while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*flag;
}
int n,m,tot,f[M],fa[M][20],siz[M],dd[M],du[M],dep[M];
struct edge
{int v,next;
}e[2*M];
void dfs(int u,int p)
{dep[u]=dep[p]+1;fa[u][0]=p;siz[u]=1;for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];for(int i=f[u];i;i=e[i].next){int v=e[i].v;if(v==p) continue;dfs(v,u);siz[u]+=siz[v];dd[u]+=dd[v]+siz[v];}
}
void dfs2(int u)
{for(int i=f[u];i;i=e[i].next){int v=e[i].v;if(v==fa[u][0]) continue;du[v]=du[u]+dd[u]-(dd[v]+siz[v])+(n-siz[v]);dfs2(v);}
}
int lca(int u,int v,int t)
{if(dep[u]<dep[v]) swap(u,v);if(t==1){for(int i=19;i>=0;i--)if(dep[fa[u][i]]>dep[v])u=fa[u][i];return u;}for(int i=19;i>=0;i--)if(dep[fa[u][i]]>=dep[v])u=fa[u][i];if(u==v) return u;for(int i=19;i>=0;i--)if(fa[u][i]^fa[v][i])u=fa[u][i],v=fa[v][i];return fa[u][0];
}
signed main()
{n=read();m=read();for(int i=1;i<n;i++){int u=read(),v=read();e[++tot]=edge{v,f[u]},f[u]=tot;e[++tot]=edge{u,f[v]},f[v]=tot;}dfs(1,0);dfs2(1);for(int i=1;i<=m;i++){int x=read(),y=read(),t=lca(x,y,0);int t2=lca(x,y,1),ans=0,d=dep[x]+dep[y]-2*dep[t]+1;if(x==t){ans+=(du[x]+dd[x]-dd[t2]-siz[t2])*siz[y];ans+=dd[y]*(n-siz[t2]);printf("%lfn",1.0*ans/(n-siz[t2])/siz[y]+d);}else if(y==t){ans+=(du[y]+dd[y]-dd[t2]-siz[t2])*siz[x];ans+=dd[x]*(n-siz[t2]);printf("%lfn",1.0*ans/(n-siz[t2])/siz[x]+d);}else{ans+=dd[x]*siz[y];ans+=dd[y]*siz[x];printf("%lfn",1.0*ans/siz[x]/siz[y]+d);}}
}