Tree

Time Limit: 20 Sec Memory Limit: 512 MB

Description

img

Input

img

Output

img

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：

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

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

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

2. 如何求 g：

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

然后我们 左右两边同乘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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#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));
    }
}