-
Notifications
You must be signed in to change notification settings - Fork 484
/
1377.cpp
32 lines (29 loc) · 759 Bytes
/
1377.cpp
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
class Solution
{
public:
double frogPosition(int n, vector<vector<int>>& edges, int t, int target)
{
if (n == 1) return 1;
g.resize(n + 1);
this->target = target;
for (auto& it : edges)
{
g[it[0]].emplace_back(it[1]);
g[it[1]].emplace_back(it[0]);
}
return dfs(-1, 1, t);
}
private:
vector<vector<int>> g;
int target;
double dfs(int fa, int cur, int t)
{
if (cur != 1 && g[cur].size() == 1 || t == 0) return cur == target;
double res = 0.0;
for (int i : g[cur])
{
if (i != fa) res = max(res, dfs(cur, i, t - 1));
}
return res / (g[cur].size() - (cur != 1));
}
};