using namespace std;
#include <iostream>
#include <vector>
#define pi pair<int,int>
#define vi vector<int>
#define ll long long
#include <algorithm>
const int siz = 1e5;
vector<pi> f[siz];
pi padre[siz];
int ans[siz];
int h[siz];
bool ch[siz];
const ll m = 1e9 + 7;
bool t;
bool fun(pi p1, pi p2) {
return p2.second < p1.second;
}
ll powe(ll a, ll b) {
if (b == 0)
return 1;
ll ans = powe(a, b / 2);
ans = (ans * ans) % m;
if (b % 2) {
ans = (ans * a) % m;
}
return ans;
}
bool dfs(int i) {
for (int j = 0; j < f[i].size(); j++) {
int fr = f[i][j].first;
if (fr != padre[i].first) {
padre[fr].first = i;
h[fr] = h[i] + 1;
f[i][j].second = !dfs(fr);
ans[i] += f[i][j].second;
}
}
sort(f[i].begin(), f[i].end(), fun);
return (bool)ans[i];
}
void dfs1(int i) {
if (i) {
int p = padre[i].first;
padre[i].second = padre[p].second;
if (f[p][0].first != i) {
padre[i].second |= f[p][0].second;
}
else if (f[p].size() > 1) {
padre[i].second |= f[p][1].second;
}
padre[i].second = !padre[i].second;
}
for (pi fr : f[i]) {
if(fr.first!=padre[i].first)
dfs1(fr.first);
}
//ans[i] += padre[i].second;
}
void dfs2(int i, int sum) {
if (t) {
if (h[i] % 2) {
//if (sum == (h[i] + 1) / 2)
ch[i] = 1;
if (f[i][0].first != padre[i].first)
dfs2(f[i][0].first, sum);
}
else if (ans[i] == 1) {
for (pi fr : f[i]) {
if (fr.first != padre[i].first)
dfs2(fr.first, sum + ans[i]);
}
}
}
else {
if (h[i] % 2==0) {
//if (sum == (h[i] + 1) / 2)
ch[i] = 1;
if (f[i][0].first != padre[i].first)
dfs2(f[i][0].first, sum);
}
else if (ans[i] == 1) {
for (pi fr : f[i]) {
if (fr.first != padre[i].first)
dfs2(fr.first, sum + ans[i]);
}
}
}
}
int main()
{
ll n,d;
cin >> n >> d;
for (int i = 0; i < n-1; i++) {
int a, b;
cin >> a >> b;
a--, b--;
f[a].push_back({ b,0 });
f[b].push_back({ a,0 });
}
dfs(0);
dfs1(0);
t = ans[0];
dfs2(0,0);
int sum = 0;
for (int i = 0; i < n; i++) {
ans[i] = ((bool)(ans[i])) || padre[i].second;
sum += ans[i];
}
ll fin=0;
sum = n - sum;
if (ans[0]) {
for (int i = 0; i < n; i++) {
if (ch[i]) {
fin += n-sum;
}
else {
fin += n;
}
}
}
else {
for (int i = 0; i < n; i++) {
if (ch[i]) {
fin += sum;
}
}
}
fin = fin%m;
cout << fin;
}
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu
// Tips for Getting Started:
// 1. Use the Solution Explorer window to add/manage files
// 2. Use the Team Explorer window to connect to source control
// 3. Use the Output window to see build output and other messages
// 4. Use the Error List window to view errors
// 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
// 6. In the future, to open this project again, go to File > Open > Project and select the .sln file
Compilation message
startrek.cpp: In function 'bool dfs(int)':
startrek.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (int j = 0; j < f[i].size(); j++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
2644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
2644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
