樹

題目大意

給你一棵有n個節點的樹，以及m個詢問，每個詢問需要你回答一個點到另一個點要經過的期望邊數

輸入樣例

4 2 1 2 2 3 3 4 1 4 3 4

輸出樣例

9 5

數據范圍

對于 $20\%$的數據,$N?10.$
對于 $40\%$的數據,$N?1000.$
另有 $20\%$的數據, 保證給定的樹是一條鏈.
對于 $100\%$的數據, $N?100000,Q?100000.$

解題思路

樹上兩點之間的距離要先求$lca$，然后可以通過前綴和來得出兩點到$lca$距離
對于前綴和我們要先得出某個點到父親節點和兒子節點的期望距離
我們設
$de{g}_x$為點$x$的度數
$dp{1}_x$為點$x$到父親節點的期望距離
$dp{2}_x$為點$x$的父親節點到點x的期望距離
我們先算$dp1$
葉子結點到父親節點的期望距離為1，因為只能往上
對于不是葉子結點的點$x$
它直接到父親節點的期望是$\frac{1}{de{g}_x}$（$\frac{1}{de{g}_x}$的概率走這條邊）
他到子節點i再回來再到父親節點的期望是$\frac{1+dp{1}_i+dp{1}_x}{de{g}_x}$
所以可以得到以下式子

$$dp{1}_x=\frac{1}{de{g}_x}+\sum _{i\in so{n}_x}\frac{1+dp{1}_i+dp{1}_x}{de{g}_x}$$
化簡式子
$$dp{1}_x=\frac{1}{de{g}_x}+\frac{de{g}_x?1}{de{g}_x}+\frac{(de{g}_x?1)dp{1}_x}{de{g}_x}+\sum _{i\in so{n}_x}\frac{dp{1}_i}{de{g}_x}$$
移項
$$\frac{dp{1}_{x}de{g}_x}{de{g}_x}?\frac{(de{g}_x?1)dp{1}_x}{de{g}_x}=\frac{1}{de{g}_x}+\frac{de{g}_x?1}{de{g}_x}+\sum _{i\in so{n}_x}\frac{dp{1}_i}{de{g}_x}$$
化簡
$$\frac{dp{1}_x}{de{g}_x}=\frac{1}{de{g}_x}+\frac{de{g}_x?1}{de{g}_x}+\sum _{i\in so{n}_x}\frac{dp{1}_i}{de{g}_x}$$
同乘$de{g}_x$
$$dp{1}_x=de{g}_x+\sum _{i\in so{n}_x}dp{1}_i$$
求出dp1后我們來求dp2
父親節點直接到目標子節點的期望是$\frac{1}{de{g}_{fa}}$
父親節點先到父親節點的父親節點然后回來再到目標子節點的期望是$\frac{1+dp{2}_{fa}+dp{2}_x}{de{g}_{fa}}$
父親節點先到其他子節點再回來再到目標子節點的期望是$\frac{1+dp{1}_i+dp{2}_x}{de{g}_{fa}}$
所以我們得到式子
$$dp{2}_x=\frac{1}{de{g}_{fa}}+\frac{1+dp{2}_{fa}+dp{2}_x}{de{g}_{fa}}+\sum _{i\in so{n}_{fa}|i=x}\frac{1+dp{1}_i+dp{2}_x}{de{g}_{fa}}$$
化簡式子
$$dp{2}_x=\frac{1}{de{g}_{fa}}+\frac{1+dp{2}_{fa}}{de{g}_{fa}}+\frac{dp{2}_x}{degfa}+\frac{de{g}_{fa}?2}{de{g}_{fa}}+\frac{(de{g}_{fa}?2)dp{2}_x}{de{g}_{fa}}+\sum _{i\in so{n}_{fa}|i=x}\frac{dp{1}_i}{de{g}_{fa}}$$
移項
$$\frac{dp{2}_{x}de{g}_{fa}}{degfa}?\frac{dp{2}_x}{degfa}?\frac{(de{g}_{fa}?2)dp{2}_x}{de{g}_{fa}}=\frac{1}{de{g}_{fa}}+\frac{1+dp{2}_{fa}}{de{g}_{fa}}+\frac{de{g}_{fa}?2}{de{g}_{fa}}+\sum _{i\in so{n}_{fa}|i=x}\frac{dp{1}_i}{de{g}_{fa}}$$
合并
$$\frac{dp{2}_x}{degfa}=\frac{1}{de{g}_{fa}}+\frac{1+dp{2}_{fa}}{de{g}_{fa}}+\frac{de{g}_{fa}?2}{de{g}_{fa}}+\sum _{i\in so{n}_{fa}|i=x}\frac{dp{1}_i}{de{g}_{fa}}$$
同乘$de{g}_{fa}$
$$dp{2}_x=dp{2}_{fa}+de{g}_{fa}+\sum _{i\in so{n}_{fa}|i=x}dp{1}_i$$
根據$dp{1}_x$的式子化簡該式子
$$\begin{gathered} \begin{array}{rl}\because de{g}_{fa}+\sum _{i\in so{n}_{fa}|i=x}dp{1}_i& =de{g}_{fa}+\sum _{i\in so{n}_{fa}}dp{1}_i?dp{1}_x\\ & =dp{1}_{fa}?dp{1}_x\end{array} \\ \therefore dp{2}_x=dp{2}_{fa}+dp{1}_{fa}?dp{1}_x \end{gathered}$$
然后求前綴和，再求$lca$
然后求$a$到$lca$再到$b$的期望步數即可

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define wyc 1000000007 using namespace std; ll n, m, x, y, z, g, tot, dep[110010], deg[110010], dp1[110010], dp2[110010], head[110010], f[110010][20]; struct rec {ll to, next; }a[210020]; void add(ll x, ll y) {a[++tot].to = y;a[tot].next = head[x];head[x] = tot;return; } void dfs1(ll x, ll fa)//記錄dp1 {f[x][0] = fa;//記錄父親dep[x] = dep[fa] + 1;//求深度dp1[x] = deg[x];for (int i = head[x]; i; i = a[i].next)if (a[i].to != fa){dfs1(a[i].to, x);dp1[x] = (dp1[x] + dp1[a[i].to]) % wyc;}return; } void dfs2(ll x, ll fa)//求dp2 {for (int i = head[x]; i; i = a[i].next)if (a[i].to != fa){dp2[a[i].to] = (dp1[x] - dp1[a[i].to] + dp2[x]) % wyc;dfs2(a[i].to, x);}return; } void dfs3(ll x, ll fa)//前綴和 {for (int i = head[x]; i; i = a[i].next)if (a[i].to != fa){dp1[a[i].to] = (dp1[a[i].to] + dp1[x]) % wyc;dp2[a[i].to] = (dp2[a[i].to] + dp2[x]) % wyc;dfs3(a[i].to, x);} return; } ll lca(ll x, ll y) {if (dep[x] < dep[y]) g = x, x = y, y = g;for (int i = 16; i >= 0; --i)if (dep[x] - (1<<i) >= dep[y]) x = f[x][i];for (int i = 16; i >= 0; --i)if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];return x == y?x:f[x][0]; } int main() {scanf("%lld%lld", &n, &m);for (int i = 1;i < n; ++i){scanf("%lld%lld", &x, &y);deg[x]++;deg[y]++;add(x, y);add(y, x);}dfs1(1, 1);dfs2(1, 1);dfs3(1, 1); for (int j = 1; j <= 16; ++j)for (int i = 1; i <= n; ++i)f[i][j] = f[f[i][j - 1]][j - 1];for (int i = 1; i <= m; ++i){scanf("%lld%lld", &x, &y);z = lca(x, y);printf("%lld\n", ((wyc + dp1[x] - dp1[z]) % wyc + (wyc + dp2[y] - dp2[z]) % wyc) % wyc);}return 0; }

總結

以上是生活随笔為你收集整理的【数学期望】【LCA】【树形DP】树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。