随机游走
题目背景：
分析：本题解法：树形DP + 倍增或树链剖分
为了方便表述，记x的父亲为father[x]，x的度数为k（则x的儿子的个数为k-1），x的儿子为son[x,1], son[x,2],..., son[x,k-1]，E[x]为由x节点走向father[x]的期望步数。
容易列出下面的式子：
我们自下而上DP，即可计算得出所有的E[x]。
同样道理，把上面的式子变一变，就可以算出由x节点走向son[x,i]的期望步数。
则从u到v的期望步数=u到lca(u,v)的期望步数+lca(u,v)到v的期望步数。我们可以利用树链剖分来求的某一段的步数，当然倍增也是可以的。
Source：
#include #include #include #include #include #include #include #include using namespace std; inline char read() { static const int IN_LEN = 1024 * 1024; static char buf[IN_LEN], *s, *t; if (s == t) { t = (s = buf) + fread(buf, 1, IN_LEN, stdin); if (s == t) return -1; } return *s++; } template inline bool R(T &x) { static char c; static bool iosig; for (c = read(), iosig = false; !isdigit(c); c = read()) { if (c == -1) return false; if (c == '-') iosig = true; } for (x = 0; isdigit(c); c = read()) x = (x << 3) + (x << 1) + (c ^ '0'); if (iosig) x = -x; return true; } const int OUT_LEN = 1024 * 1024; char obuf[OUT_LEN], *oh = obuf; inline void writechar(char c) { if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf; *oh++ = c; } template inline void W(T x) { static int buf[30], cnt; if (!x) writechar(48); else { if (x < 0) writechar('-'), x = -x; for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48; while (cnt) writechar(buf[cnt--]); } } inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); } const int MAXN = 100000 + 10; int degree[MAXN], pos[MAXN]; long long up[MAXN], down[MAXN]; int n, m, x, y, ind; struct Tree { int dep; int son; int top; int size; int father; int num; long long up; long long down; } tree[MAXN]; vector edge[MAXN]; inline void addEdge(int x, int y) { edge[x].push_back(y); edge[y].push_back(x); } inline void readin() { R(n); for (int i = 1; i < n; ++i) { R(x), R(y); degree[x]++, degree[y]++; addEdge(x, y); } } inline void dfs1(int cur, int fa) { tree[cur].father = fa; tree[cur].size = 1; tree[cur].up = degree[cur]; tree[cur].dep = tree[fa].dep + 1; for (int p = 0; p < edge[cur].size(); ++p) if (edge[cur][p] != fa) { dfs1(edge[cur][p], cur); tree[cur].up += tree[edge[cur][p]].up; tree[cur].size += tree[edge[cur][p]].size; if (!tree[cur].son || tree[edge[cur][p]].size > tree[tree[cur].son].size) tree[cur].son = edge[cur][p]; } } inline void dfs2(int cur, int fa) { long long temp = degree[cur] + tree[cur].down; for (int p = 0; p < edge[cur].size(); ++p) if (edge[cur][p] != fa) temp += tree[edge[cur][p]].up; for (int p = 0; p < edge[cur].size(); ++p) if (edge[cur][p] != fa) { tree[edge[cur][p]].down = temp - tree[edge[cur][p]].up; dfs2(edge[cur][p], cur); } } inline void dfs3(int cur, int top) { tree[cur].top = top; tree[cur].num = ++ind, pos[ind] = cur; up[ind] = tree[cur].up, down[ind] = tree[cur].down; if (tree[cur].son) dfs3(tree[cur].son, top); for (int p = 0; p < edge[cur].size(); ++p) if (!tree[edge[cur][p]].num) dfs3(edge[cur][p], edge[cur][p]); } inline void pre() { for (int i = 1; i <= n; ++i) up[i] += up[i - 1], down[i] += down[i - 1]; } inline long long solve_query(int u, int v) { long long ans = 0; while (tree[u].top != tree[v].top) { int x = tree[u].top, y = tree[v].top; if (tree[x].dep > tree[y].dep) { ans += up[tree[u].num] - up[tree[x].num - 1]; u = tree[x].father; } else { ans += down[tree[v].num] - down[tree[y].num - 1]; v = tree[y].father; } } if (u == v) return ans; if (tree[u].dep > tree[v].dep) ans += up[tree[u].num] - up[tree[v].num]; else ans += down[tree[v].num] - down[tree[u].num]; return ans; } inline void query() { R(m); while (m--) { R(x), R(y); W(solve_query(x, y)); writechar('\n'); } } int main() { // freopen("in.in", "r", stdin); readin(); dfs1(1, 1); dfs2(1, 1); dfs3(1, 1); pre(); query(); flush(); return 0; }
