[CF 629E] Famil Door and Roads

我选择先写题解再做题。

思考阶段

我们似乎可以考虑计算：总边数 以及 总长度

• 如果 $a$ 与 $b$ 有祖先关系？

总边数： 似乎是 $a$ 的子树内方案数乘 $b$ 的子树外方案数？ （方案数就是子树大小？）
总长度： 这个有点不好算了，难道是： （$a$ 的子树内所有路径总长乘 $b$ 的子树外方案数）+（$b$ 的子树外所有路径总长乘 $a$ 的子树内方案数）+（$a-b$之间链长乘总边数）？

• 如果 $a$ 与 $b$ 无祖先关系？
• 

总边数： 似乎是 $a$ 的子树内方案数乘 $b$ 的子树内方案数？
总长度： 同样与祖先情况类似吗？难道说是：（$a$ 的子树内所有路径总长乘 $b$ 的子树内方案数）+（$b$ 的子树内所有路径总长乘 $a$ 的子树内方案数）+（$a-b$之间链长乘总边数）？

打打试试看！

Code

#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define DB double
#define LL long long
#define MAXN 100005
#define Int register int
#define Mod 1000000007
using namespace std;
inline void Swap(LL &x,LL &y)
{LL Temp = x;x = y;y = Temp;
}
inline LL Abs(LL x)
{if (x > 0)return x;return - x;
}
inline LL Min(LL x,LL y)
{return x < y ? x : y;
}
inline LL Max(LL x,LL y)
{return x > y ? x : y;
}
inline void read(LL &x)
{x = 0;LL f = 1;char s = getchar();while (s < '0' || s > '9'){if (s == '-')f = -1;s = getchar();}while (s >= '0' && s <= '9'){x = (x << 3) + (x << 1) + (s ^ 48);s = getchar();}x *= f;
}
vector<LL> G[MAXN];
LL f[MAXN][18], Dep[MAXN];
void Build(LL x,LL Pre)
{f[x][0] = Pre;Dep[x] = Dep[Pre] + 1;for (Int i = 1; i < 18; ++ i)f[x][i] = f[f[x][i - 1]][i - 1];int l = G[x].size();for (Int i = 0; i < l; ++ i){LL to = G[x][i];if (to == Pre)continue;Build(to, x);}
}
void Adjust(LL &u,LL To)
{for (Int i = 17; i >= 0; -- i)if (Dep[f[u][i]] >= To)u = f[u][i];
}
LL Lca(LL u,LL v)
{if (u == 1 || v == 1)return 1;if (Dep[u] > Dep[v])Adjust(u, Dep[v]);else if (Dep[u] < Dep[v])Adjust(v, Dep[u]);if (u == v)return u;for (Int i = 17; i >= 0; -- i)if (f[u][i] != f[v][i])u = f[u][i], v = f[v][i];return f[u][0];
}
LL Size[MAXN], Length[MAXN], Other[MAXN];
void Prepare(LL x,LL Pre)
{Size[x] = 1;int l = G[x].size();for (Int i = 0; i < l; ++ i){LL to = G[x][i];if (to == Pre)continue;Prepare(to, x);Size[x] += Size[to];Length[x] += Length[to] + Size[to];}
}
LL Zb, Zc;
void GetOther(LL x,LL Pre)
{int l = G[x].size();}
int main()
{LL n, m;read( n ); read( m );for (Int i = 1; i < n; ++ i){LL u, v;read( u ); read( v );G[u].push_back( v );G[v].push_back( u );  }Build(1, 1);Prepare(1, 1);GetOther(1, 1);for (Int i = 1; i <= m; ++ i){Zb = Zc = 0;LL a, b;read( a ); read( b );// 判断是否有祖先关系：LL ta = a, tb = b;if (Dep[ta] > Dep[tb])Adjust(ta, Dep[tb]);else if (Dep[tb] > Dep[ta])Adjust(tb, Dep[ta]);if (ta == tb) // 有祖先关系{if (Dep[a] < Dep[b]) // b是祖先Swap(a, b);Zb = Size[a] * (Size[1] - Size[b] + 1);
//			printf("Cd : %lld %lld %lld\n", Length[1], Length[a], Length[b]);Zc = Length[a] * (Size[1] - Size[b] + 1) + Other[b] * Size[a] + (Dep[a] - Dep[b]) * Size[a] * (Size[1] - Size[b] + 1);}else // 无祖先关系 {LL Mid = Lca(a, b);LL Lc = Dep[a] + Dep[b] - Dep[Mid] * 2;Zb = Size[a] * Size[b];Zc = Length[a] * Size[b] + Length[b] * Size[a] + Lc * Zb;}printf("Ts : %lld %lld\n", Zc, Zb);printf("%.10f\n", (0.0 + Zc + Zb) / Zb);}return 0;
}