#P1730. 第5题-小美迷路
-
2000ms
Tried: 99
Accepted: 13
Difficulty: 10
所属公司 :
美团
时间 :2024年3月23日
-
算法标签>树
第5题-小美迷路
题目思路
本题难度较大，需要一定的图论基础。没有了解过LCA和逆元的可以先去学习一下。
树上任意两个点的路径其实是唯一的，所以到达的概率需要通过数个可供选择的邻居数量的倒数相乘，设cnti是节点i的邻居数量，由于概率需要取模，所以我们应用快速幂求乘法逆元得到概率取模后的值。
这里简单介绍一下逆元的知识，假设x * y % mod == 1，那么我们就称y是x的逆元，所以我们其实就是求类似于cnti的逆元。
首先考虑简单的情况，对于两个点u,v，如果它们在树上是祖先-子孙关系，那么通过dfs枚举到子孙v时，我们可以统计从根结点（这个可以自己定，这里我们定为0）到v这条路径上所有节点的1/(cnti−1)的累乘值：
比如对于1-2-3来说，这在树上是一条链，那么1记录的就是1/(cnt1−1)，2记录的就是1/(cnt1−1)∗1/(cnt2−1)，我们将这个值保存在path中。
假设从u->v：
- 是v的子孙，那么从u出发，它一开始可以选择的节点数量应该是所有邻居都可以选，所以概率是1/cntu,而中间的那些节点，由于已经从父节点过来，所以可以选择节点是邻居的数量减一。 那么直接统计
path[fa[v]] / path[u] * (1/cnt[u])即可，这里fa[v]表示我们dfs遍历时v的父节点，注意这里的除法依旧需要换成乘法逆元。 - 如果是v是祖先，依旧是类似地，u依旧可以选择所有邻居，统计
path[fa[u]] / path[v] * (1/cnt[u])即可。
考虑复杂的情况，假设u和v不是在同一条链上，那么我们可以找到它的最近公共祖先LCA假设是z，那么路径其实是u->z, z->v分开两条考虑，但是值得注意的是z->v这条路上，z作为起始点其实能选的邻居数量会少一个，因为从u->z这条路上经过了它，不能走原来的路。
求LCA可以通过倍增的思想在O(nlogn)的时间内求出。
总的时间复杂度为O(nlogn)，可以参考代码理解。
代码
C++
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second
#define endl '\n'
const int fastio = []() {
cin.tie(0)->sync_with_stdio(false);
return 0;
}();
int main() {
const int mod = 1e9 + 7;
int n, m;
cin >> n;
vector<vector<int>> g(n);
for (int i = 1, u, v;i < n;++ i) {
cin >> u >> v;
-- u, -- v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<array<int, 17>> f(n, {0});
vector<int> dep(n, 0);
// 快速幂用于求逆元
auto qmi = [&](LL a, LL k) -> LL {
LL res = 1;
while(k) {
if (k & 1) {
res = res * a % mod;
}
a = a * a % mod;
k >>= 1;
}
return res;
};
// 求LCA使用的倍增数组f
function<void(int, int)> dfs1 = [&](int u, int fa) -> void {
f[u][0] = fa;
for (int i = 1;i < 17;++ i) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
for (int v: g[u]) if (v ^ fa) {
dep[v] = dep[u] + 1;
dfs1(v, u);
}
};
// 求LCA的函数
function<int(int, int)> LCA = [&](int a, int b) -> int {
if(dep[a] < dep[b]) swap(a,b);
for(int i = 16;~i;i --)
if(dep[f[a][i]] >= dep[b]) a = f[a][i];
if(a == b) return a;
for(int i = 16;~i;i --)
if(f[a][i] != f[b][i])
a = f[a][i],b = f[b][i];
return f[a][0];
};
dfs1(0, 0);
cin >> m;
vector<vector<PII>> st(n), ed(n);
vector<int> ans(m, 1);
for (int i = 0, u, v;i < m;++ i) {
cin >> u >> v;
-- u, -- v;
int z = LCA(u, v);
if (u != z) {
st[u].emplace_back(z, i);
if (v != z) {
ed[v].emplace_back(z, i);
// 注意z->v的过程中初始可以选择的邻居数量会少1
ans[i] = qmi(g[z].size() - 1, mod - 2) * qmi(qmi(g[z].size(), mod - 2), mod - 2) % mod;
}
} else {
ed[v].emplace_back(u, i);
}
}
vector<LL> path(n, 0);
// 树上统计
function<void(int, int)> dfs2 = [&](int u, int fa) -> void {
for (auto&t: ed[u]) {
LL tmp = path[fa] * qmi(path[t.x], mod - 2) % mod * qmi(g[t.x].size(), mod - 2) % mod;
ans[t.y] = ans[t.y] * tmp % mod;
}
if (u) path[u] = path[fa] * qmi(g[u].size() - 1, mod - 2) % mod;
else path[u] = qmi(g[u].size(), mod - 2);
for (auto&t: st[u]) {
LL tmp = path[fa] * qmi(g[u].size(), mod - 2) % mod * qmi(path[t.x], mod - 2) % mod;
ans[t.y] = ans[t.y] * tmp % mod;
}
for (int v: g[u]) if (v ^ fa) {
dfs2(v, u);
}
};
dfs2(0, 0);
for (int v: ans) cout << v << endl;
return 0;
}
python
import os,sys,random,threading
#sys.exit() 退出程序
#sys.setrecursionlimit(10**6) #调整栈空间
from random import randint,choice,shuffle
#randint(a,b)从[a,b]范围随机选择一个数
#choice(seq)seq可以是一个列表,元组或字符串,从seq中随机选取一个元素
#shuffle(x)将一个可变的序列x中的元素打乱
from copy import deepcopy
from io import BytesIO,IOBase
from types import GeneratorType
from functools import lru_cache,reduce
#reduce(op,迭代对象)
from bisect import bisect_left,bisect_right
#bisect_left(x) 大于等于x的第一个下标
#bisect_right(x) 大于x的第一个下标
from collections import Counter,defaultdict,deque
from itertools import accumulate,combinations,permutations
#accumulate(a)用a序列生成一个累积迭代器，一般list化前面放个[0]做前缀和用
#combinations(a,k)a序列选k个 组合迭代器
#permutations(a,k)a序列选k个 排列迭代器
from heapq import heapify,heappop,heappush
#heapify将列表转为堆
from typing import Generic,Iterable,Iterator,TypeVar,Union,List
from string import ascii_lowercase,ascii_uppercase,digits
#小写字母，大写字母，十进制数字
from math import ceil,floor,sqrt,pi,factorial,gcd,log,log10,log2,inf
#ceil向上取整，floor向下取整 ，sqrt开方 ，factorial阶乘
from decimal import Decimal,getcontext
#Decimal(s) 实例化Decimal对象,一般使用字符串
#getcontext().prec=100 修改精度
from sys import stdin, stdout, setrecursionlimit
input = lambda: sys.stdin.readline().rstrip("\r\n")
MI = lambda :map(int,input().split())
li = lambda :list(MI())
ii = lambda :int(input())
mod = int(1e9 + 7) #998244353
inf = 1<<60
py = lambda :print("YES")
pn = lambda :print("NO")
DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 右下左上
DIRS8 = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0),(-1, 1)] # →↘↓↙←↖↑↗
class HLD:
def __init__(self, g, root):
#无论是点还是dfn还是dep，都从1开始，默认0是无
n=len(g)
self.g=g
self.fa=[0]*(n+5) #父节点，0表示无父节点
self.size=[1]*(n+5) #子树大小
self.dep=[0]*(n+5) #深度，根深度为1
self.son=[0]*(n+5) #重儿子，0表示无儿子
self.dfn=[0]*(n+5) #dfs序，子树终点的dfs序是dfn[i]+size[i]-1
self.top=[0]*(n+5) #所在重链起点，起点就是自己
self.rank=[0]*(n+5) #dfs序为i的节点编号
fa=self.fa;size=self.size;dep=self.dep;son=self.son
dfn=self.dfn;top=self.top;rank=self.rank
stk=[[root,0,0]] #node,flag,fa
dep[root]=1
while stk:
u,flag,father=stk.pop()
if flag:
for v in g[u]:
if v!=father:
size[u]+=size[v]
if son[u]==0 or size[v]>size[son[u]]:
son[u]=v
else:
stk.append([u,1,father])
for v in g[u]:
if v!=father:
stk.append([v,0,u])
fa[v]=u
dep[v]=dep[u]+1
stk=[[root,root]]
tot=1
while stk:
u,tops=stk.pop()
dfn[u]=tot
rank[tot]=u
tot+=1
top[u]=tops
if son[u]==0:
continue
for v in g[u]:
if v!=fa[u] and v!=son[u]:
stk.append([v,v])
stk.append([son[u],tops])
def lca(self,u,v): #求u和v的最近公共祖先节点
fa=self.fa;size=self.size;dep=self.dep;son=self.son
dfn=self.dfn;top=self.top;rank=self.rank
while top[u]!=top[v]:
if dep[top[u]]>dep[top[v]]:
u=fa[top[u]]
else:
v=fa[top[v]]
return v if dep[u]>dep[v] else u
def dis(self,u,v):
dep=self.dep
return dep[u]+dep[v]-2*dep[self.lca(u,v)]
def kth_fa(self,root,k): #求root节点的第k个祖先
fa=self.fa;size=self.size;dep=self.dep;son=self.son
dfn=self.dfn;top=self.top;rank=self.rank
if k>=dep[root]: #无第k个祖先返回-1
return -1
while True:
u=top[root]
if dfn[root]-k>=dfn[u]:
return rank[dfn[root]-k]
k-=dfn[root]-dfn[u]+1
root=fa[u]
def route_query(self,u,v): #查询u到v简单路径
fa=self.fa;size=self.size;dep=self.dep;son=self.son
dfn=self.dfn;top=self.top;rank=self.rank
route=[]
while top[u]!=top[v]:
if dep[top[u]]<dep[top[v]]:
u,v=v,u
route.append((dfn[top[u]],dfn[u]))
u=fa[top[u]]
if dep[u]>dep[v]:
u,v=v,u
route.append((dfn[u],dfn[v]))
return route
def path(self,start,end): #得到start到end简单路径的所有节点
fa=self.fa;size=self.size;dep=self.dep;son=self.son
dfn=self.dfn;top=self.top;rank=self.rank
mid=self.lca(start,end)
ps=[]
while start!=mid:
ps.append(start)
start=fa[start]
pe=[]
while end!=mid:
pe.append(end)
end=fa[end]
return ps+[mid]+pe[::-1]
def bootstrap(f, stack=[]): #yield
def wrappedfunc(*args, **kwargs):
if stack:
return f(*args, **kwargs)
else:
to = f(*args, **kwargs)
while True:
if type(to) is GeneratorType:
stack.append(to)
to = next(to)
else:
stack.pop()
if not stack:
break
to = stack[-1].send(to)
return to
return wrappedfunc
n=ii()
g=[[] for _ in range(n+1)]
inv_list=[0]*(n+1)
inv_list[1]=1
for i in range(2,n+1):
inv_list[i]=(mod-mod//i)*inv_list[mod%i]%mod
for _ in range(n-1):
u,v=li()
g[u]+=[v]
g[v]+=[u]
hld=HLD(g,1)
dep=hld.dep
def inv(x):
if x<=n:
return inv_list[x]
return pow(x,mod-2,mod)
pre1=[0]*(n+1)
pre2=[0]*(n+1)
@bootstrap
def dfs(u,fa):
if u==1:
pre1[u]=pre2[u]=1
else:
t=len(g[fa]) if fa==1 else (len(g[fa])-1)
pre1[u]=pre1[fa]*inv(t)%mod
pre2[u]=pre2[fa]*len(g[fa])*inv(t)*inv(len(g[u]))%mod
for v in g[u]:
if v!=fa:
yield dfs(v,u)
yield None
dfs(1,-1)
def cal(x,y):
if x==1:
return pre1[y]
if y==1:
return pre2[x]
if dep[x]>dep[y]:
return pre2[x]*inv(pre2[y]*len(g[y])*inv(len(g[y])-1))%mod
return pre1[y]*inv(pre1[x])*(len(g[x])-1)*inv(len(g[x]))%mod
q=ii()
for _ in range(q):
s,t=li()
lca=hld.lca(s,t)
if s==t:
print(1)
elif lca==s or lca==t:
print(cal(s,t))
elif lca==1:
print(pre2[s]*pre1[t]*len(g[1])*inv(len(g[1])-1)%mod)
else:
print(cal(s,lca)*cal(lca,t)*len(g[lca])*inv(len(g[lca])-1)%mod)
java
import java.io.*;
import java.util.*;
public class Main {
static Kattio sc = new Kattio();
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
public static void main(String[] args) {
// int t = sc.nextInt();
int t = 1;
while (t-- > 0) {
solve();
}
out.flush();
out.close();
}
static long[] inv;
static List<Integer>[] graph;
static int[] h;
static int[] f;
static int[][] pa;
static long[][] pb;
public static void solve() {
int n = sc.nextInt();
inv = new long[n];
graph = new List[n];
h = new int[n];
f = new int[n];
pa = new int[n][18];
pb = new long[n][18];
for (int i = 1; i < n; i++) {
inv[i] = inv(i);
}
inv[0] = 1;
Arrays.setAll(graph, v -> new ArrayList<>());
for (int i = 0; i < n - 1; i++) {
int u = sc.nextInt() - 1, v = sc.nextInt() - 1;
graph[u].add(v);
graph[v].add(u);
}
f[0] = -1;
dfs(0);
for (int i = 0; i < n; i++) {
pa[i][0] = f[i];
pb[i][0] = inv[graph[i].size() - 1];
}
for (int j = 0; j < 17; j++) {
for (int i = 0; i < n; i++) {
if (pa[i][j] != -1) {
pa[i][j + 1] = pa[pa[i][j]][j];
pb[i][j + 1] = pb[i][j] * pb[pa[i][j]][j] % MOD;
}
}
}
int q = sc.nextInt();
while (q-- > 0) {
int s = sc.nextInt() - 1, t = sc.nextInt() - 1;
if (s == t) {
out.println(1);
continue;
}
int lca = lca(s, t);
long res = inv[graph[s].size()];
s = f[s];
int d = s == -1 ? -1 : h[s] - h[lca] + (t == lca ? 0 : 1);
if (d > 0) {
for (int i = 17; i >= 0; i--) {
if ((d >> i & 1) != 0) {
res = res * pb[s][i] % MOD;
s = pa[s][i];
}
}
}
t = f[t];
d = t == -1 ? -1 : h[t] - h[lca];
if (d > 0) {
for (int i = 17; i >= 0; i--) {
if ((d >> i & 1) != 0) {
res = res * pb[t][i] % MOD;
t = pa[t][i];
}
}
}
out.println(res);
}
}
public static int lca(int x, int y) {
int min = Math.min(h[x], h[y]);
if (h[x] == min) {
y = jump(y, h[y] - min);
} else {
x = jump(x, h[x] - min);
}
for (int i = 17; i >= 0; i--) {
if (pa[x][i] != pa[y][i]) {
x = pa[x][i];
y = pa[y][i];
}
}
return x == y ? x : f[x];
}
public static int jump(int cur, int d) {
for (int i = 0; i <= 17; i++) {
if (cur < 0) {
break;
}
if ((d >> i & 1) != 0) {
cur = pa[cur][i];
}
}
return cur;
}
public static void dfs(int cur) {
for (int next : graph[cur]) {
if (f[cur] == next) {
continue;
}
h[next] = h[cur] + 1;
f[next] = cur;
dfs(next);
}
}
// static final long MAX = (long) 2e18;
// static final long MIN = -(long) 2e18;
static final int MAX = 0x3fffffff;
static final int MIN = -0x3fffffff;
static final int MOD = 1000000007;
public static long gcd(long a, long b) {
return a % b == 0 ? b : gcd(b, a % b);
}
public static long lcm(long a, long b) {
return a / gcd(a, b) * b;
}
public static long pow(long a, long b) {
long res = 1;
while (b > 0) {
if ((b & 1) != 0) {
res = res * a % MOD;
}
a = a * a % MOD;
b >>= 1;
}
return res;
}
public static long inv(long a) {
return pow(a, MOD - 2);
}
public static boolean linearEquation(long[] ans, long a, long b, long m) {
long d = ext_gcd(ans, a, b);
if (m % d != 0) {
return false;
}
long n = m / d;
ans[0] *= n;
ans[1] *= n;
return true;
}
public static long ext_gcd(long[] ans, long a, long b) {
if (b == 0) {
ans[0] = 1;
ans[1] = 0;
return a;
}
long res = ext_gcd(ans, b, a % b);
long tmp = ans[0];
ans[0] = ans[1];
ans[1] = tmp - a / b * ans[1];
return res;
}
public static int[] getZ(char[] str) {
int N = str.length;
int[] z = new int[N];
z[0] = N;
for (int i = 1, l = 0, r = 0; i < N; i++) {
z[i] = Math.max(Math.min(z[i - l], r - i + 1), 0);
while (i + z[i] < N && str[z[i]] == str[i + z[i]]) {
l = i;
r = i + z[i];
z[i]++;
}
}
return z;
}
static class Kattio extends PrintWriter {
static BufferedReader r;
static StringTokenizer st;
public Kattio() {
this(System.in, System.out);
}
public Kattio(InputStream i, OutputStream o) {
super(o);
r = new BufferedReader(new InputStreamReader(i));
}
public Kattio(String input, String out) throws IOException {
super(out);
r = new BufferedReader(new FileReader(input));
}
public String next() {
try {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(r.readLine());
}
return st.nextToken();
} catch (Exception e) {
// TODO: handle exception
return null;
}
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
}
题目描述
小美在树上迷路了，位于s节点，但他想去t节点。小美很精明，他每次都会选一条之前没有走过的路走，他想知道，他走到t的概率是多少？
包含多次询问，每次输出概率对109+7取余后的结果。可以证明x是唯一的。
如果最后答案为分数，则最简分式后的形式为ba，其中a,b互质。那么输出整数x使b∗x≡a(mod109+7)且0≤x<109+7。
输入描述
第一行输入一个整数n(≤2∗105)表示树节点个数。
接下来n−1行，每行为u,v ,表示树上的边。
接下来一行，输入一个整数q(≤2∗105)，代表询问次数。
接下来q行，每行为s,t表示询问。
输出描述
输出q行，每行输出一个整数表示概率
样例
输入
3
1 2
1 3
2
2 3
1 3
输出
1
500000004
说明
第一个询问，有1的概率从节点2走到节点1，然后有1的概率从节点1走到节点3。因此答案为1mod109+7=1
第二个询问，有1/2的概率从节点1走到节点2，有1/2的概率从节点1走到节点3。答案为1/2，按公式取余后结果为500000004