[期望DP]Tree

Tree

Time Limit: 20 Sec Memory Limit: 512 MB

Description

Input

Output

Sample Input

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

Sample Output

9
　　5

HINT

N <= 100000, Q <= 100000.

Solution

首先，这必然是一道期望DP。

由于E(Σx) = ΣE(x)。所以我们令 f[u] 表示从 u -> fa 的期望步数，令 g[u] 表示从 fa -> u 的期望步数。显然，求出这两个东西，再求个LCA就解决改题了。

1. 如何求 f：

我们先给出普通的关系：，

然后我们 左右两边同乘d，移项一下即可得到：f[u] = 1 + Σ(1 + f[x])。

这个方程表示什么呢？1/d的概率直接走到fa，花1步走到其它点，然后再回来。

2. 如何求 g：

我们先给出普通的关系：，

然后我们 左右两边同乘d，移项一下即可得到：g[u] = 1 + (1 + g[fa]) + Σ(1 + f[x])。注意，如果 u = root，则不应该有(1 + g[fa])，因为其没有fa。

这个方程表示什么呢？1/d的概率直接走到u，花1步走到fa的fa，然后走回fa，再下去到u；花1步走到fa的其它儿子，然后再上来，再到u。

这样得到f、g以后，DFS求一下和，树链剖分求一个LCA，直接输出答案即可。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long s64;
typedef unsigned int u32;

const int ONE = 1e6 + 5;
const int MOD = 1e9 + 7;

int n, Q;
int x, y;
int next[ONE], first[ONE], go[ONE], tot;
int f[ONE], g[ONE];
int sum_f[ONE], sum_g[ONE];

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

void Add(int u, int v)
{
    next[++tot] = first[u];    first[u] = tot;    go[tot] = v;
    next[++tot] = first[v];    first[v] = tot;    go[tot] = u;
}

namespace tree
{
    int son[ONE], size[ONE], top[ONE], fa[ONE], Dep[ONE];

    void dfs1(int u, int father)
    {
        size[u] = 1;
        fa[u] = father;
        Dep[u] = Dep[father] + 1;
        for(int e = first[u]; e; e = next[e])
        {
            int v = go[e];
            if(v == father) continue;
            dfs1(v, u);
            size[u] += v;
            if(size[son[u]] < size[v]) son[u] = v;
        }
    }

    void dfs2(int u, int father)
    {
        if(int v = son[u])
            top[v] = top[u], dfs2(v, u);
        for(int e = first[u]; e; e = next[e])
        {
            int v = go[e];
            if(v == father || v == son[u]) continue;
            dfs2(top[v] = v, u);
        }
    }

    int LCA(int u, int v)
    {
        while(top[u] != top[v])
        {
            int &x = Dep[top[u]] > Dep[top[v]] ? u : v;
            x = fa[top[x]];
        }
        return Dep[u] < Dep[v] ? u : v;
    }
}

void dfs_f(int u, int father)
{
    f[u] = 1;
    for(int e = first[u]; e; e = next[e])
    {
        int v = go[e];
        if(v == father) continue;
        dfs_f(v, u);
        f[u] = (f[u] + f[v] + 1) % MOD;
    }
}

void dfs_g(int u, int father)
{
    int res = 0;
    for(int e = first[u]; e; e = next[e])
    {
        int v = go[e];
        if(v == father) continue;
        res = (res + 1 + f[v]) % MOD;
    }

    for(int e = first[u]; e; e = next[e])
    {
        int v = go[e];
        if(v == father) continue;
        g[v] = 1 + (res - 1 - f[v] + MOD) % MOD;
        if(u != 1) g[v] = (g[v] + 1 + g[u]) % MOD;
        dfs_g(v, u);
    }
}

void Dfs(int u, int father)
{
    sum_g[u] = (sum_g[father] + g[u]) % MOD;
    sum_f[u] = (sum_f[father] + f[u]) % MOD;
    for(int e = first[u]; e; e = next[e])
    {
        int v = go[e];
        if(v == father) continue;
        Dfs(v, u);
    }
}

int dist(int u, int v)
{
    int LCA = tree::LCA(u, v), res = 0;
    res = ((s64)res + sum_f[u] - sum_f[LCA] + MOD) % MOD;
    res = ((s64)res + sum_g[v] - sum_g[LCA] + MOD) % MOD;
    return res;
}

int main()
{
    n = get();    Q = get();
    for(int i = 1; i < n; i++)
    {
        x = get();    y = get();
        Add(x, y);
    }

    tree::top[1] = 1, tree::dfs1(1, 0), tree::dfs2(1, 0);
    dfs_f(1, 0), dfs_g(1, 0);
    Dfs(1, 0);

    while(Q--)
    {
        x = get();    y = get();
        printf("%d\n", dist(x, y));
    }
}