#include <bits/stdc++.h>
using namespace std;
typedef __int128 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)
{
if (visited[i]) return;
visited[i] = true;
for (ll x : graph[i])
{
if (!visited[x])
{
getWinningStates(x, graph, winning, visited);
if (!winning[x]) winning[i] = true;
}
}
}
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];
}
ll solve(ll i, vv &graph, vb &isWinning, v &res, vb &visited, bool shouldWin, v &subtreeSize, ll winningCount, ll losingCount)
{
ll N = graph.size();
if (visited[i]) return 0;
visited[i] = true;
if (shouldWin)
{
if (isWinning[i])
{
ll losingChildren = 0;
ll losingChild;
for (ll x : graph[i])
if (!visited[x] && !isWinning[x])
{
losingChildren++;
losingChild = x;
}
if (losingChildren == 1)
{
res[i] += (N * (subtreeSize[i] - subtreeSize[losingChild])) % mod;
res[i] += solve(losingChild, graph, isWinning, res, visited, false, subtreeSize, winningCount, losingCount);
res[i] %= mod;
return res[i];
}
else
{
res[i] = (N * subtreeSize[i]) % mod;
return res[i];
}
}
else
{
res[i] += losingCount;
for (ll x : graph[i])
{
if (!visited[x])
{
res[i] += solve(x, graph, isWinning, res, visited, false, subtreeSize, winningCount, losingCount);
}
}
res[i] %= mod;
return res[i];
}
}
else
{
//should be losing - all children should be winning
if (!isWinning[i])
{
res[i] += winningCount;
for (ll x : graph[i])
{
if (!visited[x])
res[i] += solve(x, graph, isWinning, res, visited, true, subtreeSize, winningCount, losingCount);
}
res[i] %= mod;
return res[i];
}
else
{
ll losingChildren = 0, losing;
for (ll x : graph[i])
{
if (!visited[x] && !isWinning[x])
{
losingChildren++; losing = x;
}
}
if (losingChildren > 1) return 0;
res[i] = solve(losing, graph, isWinning, res, visited, true, subtreeSize, winningCount, losingCount);
return res[i];
}
}
}
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);
}
vb isWinning(N), visited(N, false);
getWinningStates(0, graph, isWinning, visited);
ll winningCount = 0, losingCount = 0;
for (auto x : isWinning)
{
if (x) winningCount++;
else losingCount++;
}
v subtreeSize(N, 0);
getSubtreeSize(0, graph, subtreeSize);
v dp(N, 0);
visited = vb(N, false);
solve(0, graph, isWinning, dp, visited, true, subtreeSize, winningCount, losingCount);
cout << (long long)dp[0] << "\n";
return 0;
}
Compilation message
startrek.cpp: In function 'll solve(ll, vv&, vb&, v&, vb&, bool, v&, ll, ll)':
startrek.cpp:130:27: warning: 'losing' may be used uninitialized in this function [-Wmaybe-uninitialized]
130 | res[i] = solve(losing, graph, isWinning, res, visited, true, subtreeSize, winningCount, losingCount);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
