#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll,ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
const ll INF = 1e18;
const ll mod = 1e9 + 7;
ll modPow(ll a, ll b)
{
if (b == 0) return 1;
ll res = modPow(a, b / 2);
res = (res * res) % mod;
if (b % 2 == 1) res = (res * a) % mod;
return res;
}
void getWinningStates(ll i, vv &graph, vb &winning, vb &visited, v &losingChildrenCount)
{
if (visited[i]) return;
visited[i] = true;
for (ll x : graph[i])
{
if (!visited[x])
{
getWinningStates(x, graph, winning, visited, losingChildrenCount);
if (!winning[x])
{
winning[i] = true;
losingChildrenCount[i]++;
}
}
}
}
void winningAsRoot(ll i, vv &graph, vb &visited, v &losingChildrenCount, vb &res, ll par)
{
if (visited[i]) return;
visited[i] = true;
if (par != -1)
{
if (losingChildrenCount[i] == 0) losingChildrenCount[par]--;
if (losingChildrenCount[par] == 0) losingChildrenCount[i]++;
}
res[i] = losingChildrenCount[i] > 0;
for (ll x : graph[i])
{
winningAsRoot(x, graph, visited, losingChildrenCount, res, i);
}
if (par != -1)
{
if (losingChildrenCount[par] == 0) losingChildrenCount[i]--;
if (losingChildrenCount[i] == 0) losingChildrenCount[par]++;
}
}
ll getSubtreeSize(ll i, vv &graph, v &res)
{
if (res[i] != 0) return 0;
res[i] = 1;
for (ll x : graph[i]) res[i] += getSubtreeSize(x, graph, res);
return res[i];
}
p operator+(p a, p b)
{
return p(a.f + b.f, a.s + b.s);
}
void operator+=(p &a, p b)
{
a.f += b.f; a.s += b.s;
}
p operator%(p a, ll mod)
{
return p(a.f % mod, a.s % mod);
}
void operator%=(p &a, ll mod)
{
a = a % mod;
}
void solve(ll i, vv &graph, vb &isWinning, vvp &res, vb &visited, v &subtreeSize)
{
ll N = graph.size();
visited[i] = true;
for (ll x : graph[i]) if (!visited[x]) solve(x, graph, isWinning, res, visited, subtreeSize);
ll losingChildren = 0;
ll losingChild;
for (ll x : graph[i])
{
if (!visited[x] && !isWinning[x])
{
losingChildren++;
losingChild = x;
}
}
if (losingChildren == 0)
{
res[i][1] = p(N, mod - 1);
for (ll x : graph[i])
{
if (!visited[x])
{
res[i][1] += res[x][0];
}
}
res[i][0] = p(0, 1);
for (ll x : graph[i])
{
if (!visited[x])
res[i][0] += res[x][1];
}
res[i][0] %= mod;
}
else if (losingChildren == 1)
{
res[i][1] = p((N * (subtreeSize[i] - subtreeSize[losingChild])) % mod, 0);
res[i][1] += res[losingChild][0];
res[i][0] = res[losingChild][1];
}
else
{
res[i][0] = p(0, 0);
res[i][1] = p((N * subtreeSize[i]) % mod, 0);
}
res[i][1] %= mod;
visited[i] = false;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
long long N, D;
cin >> N >> D;
vv graph(N);
for (ll i= 0; i < N - 1; i++)
{
long long a, b;
cin >> a >> b;
a--; b--;
graph[a].pb(b);
graph[b].pb(a);
}
vp amountOfWaysToWin(N);
for (ll i= 0; i < N; i++)
{
vb isWinning(N), visited(N, false);
v losingChildrenCount(N, 0);
getWinningStates(i, graph, isWinning, visited, losingChildrenCount);
vb winAsRoot(N, false);
visited = vb(N, false);
winningAsRoot(i, graph, visited, losingChildrenCount, winAsRoot, -1);
ll winningCount = 0, losingCount = 0;
for (auto x : winAsRoot)
{
if (x) winningCount++;
else losingCount++;
}
v subtreeSize(N, 0);
getSubtreeSize(i, graph, subtreeSize);
vvp dp(N, vp(2, p(0, 0)));
visited = vb(N, false);
solve(i, graph, isWinning, dp, visited, subtreeSize);
amountOfWaysToWin[i] = dp[i][1];
}
vb isWinning(N), visited(N, false);
v losingChildrenCount(N, 0);
getWinningStates(0, graph, isWinning, visited, losingChildrenCount);
vb winAsRoot(N, false); visited = vb(N, false);
winningAsRoot(0, graph, visited, losingChildrenCount, winAsRoot, -1);
ll winningCount = 0, losingCount = 0;
for (auto x : winAsRoot)
{
if (x) winningCount++;
}
p sum = p(0, 0);
for (auto x : amountOfWaysToWin) sum += x;
sum %= mod;
ll weighted = winningCount, absolute = 1;
for (ll i = 1; i < D; i++)
{
weighted = sum.f * absolute + sum.s * weighted;
weighted %= mod;
absolute *= (N * N) % mod;
absolute %= mod;
}
cout << (weighted * amountOfWaysToWin[0].s + absolute * amountOfWaysToWin[0].f) % mod << "\n";
return 0;
}
Compilation message
startrek.cpp: In function 'int main()':
startrek.cpp:196:26: warning: unused variable 'losingCount' [-Wunused-variable]
196 | ll winningCount = 0, losingCount = 0;
| ^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
68 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Execution timed out |
1010 ms |
348 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
78 ms |
604 KB |
Output is correct |
8 |
Correct |
102 ms |
720 KB |
Output is correct |
9 |
Correct |
69 ms |
604 KB |
Output is correct |
10 |
Correct |
72 ms |
604 KB |
Output is correct |
11 |
Correct |
73 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
78 ms |
604 KB |
Output is correct |
8 |
Correct |
102 ms |
720 KB |
Output is correct |
9 |
Correct |
69 ms |
604 KB |
Output is correct |
10 |
Correct |
72 ms |
604 KB |
Output is correct |
11 |
Correct |
73 ms |
604 KB |
Output is correct |
12 |
Execution timed out |
1077 ms |
26300 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
78 ms |
604 KB |
Output is correct |
8 |
Correct |
102 ms |
720 KB |
Output is correct |
9 |
Correct |
69 ms |
604 KB |
Output is correct |
10 |
Correct |
72 ms |
604 KB |
Output is correct |
11 |
Correct |
73 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
67 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
80 ms |
668 KB |
Output is correct |
22 |
Correct |
88 ms |
604 KB |
Output is correct |
23 |
Correct |
69 ms |
600 KB |
Output is correct |
24 |
Correct |
71 ms |
604 KB |
Output is correct |
25 |
Correct |
74 ms |
604 KB |
Output is correct |
26 |
Correct |
77 ms |
604 KB |
Output is correct |
27 |
Correct |
88 ms |
856 KB |
Output is correct |
28 |
Correct |
45 ms |
344 KB |
Output is correct |
29 |
Correct |
72 ms |
604 KB |
Output is correct |
30 |
Correct |
100 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
78 ms |
604 KB |
Output is correct |
8 |
Correct |
102 ms |
720 KB |
Output is correct |
9 |
Correct |
69 ms |
604 KB |
Output is correct |
10 |
Correct |
72 ms |
604 KB |
Output is correct |
11 |
Correct |
73 ms |
604 KB |
Output is correct |
12 |
Execution timed out |
1077 ms |
26300 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
68 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Execution timed out |
1010 ms |
348 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |