#include <bits/stdc++.h>
#define int long long int
#define lli int
#define ld long double
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
using namespace std;
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const int N = 1e5 + 5;
const int INF = 1e9 + 500;
const int MOD = 1e9 + 7;
int add(int x, int y) {
if(x + y >= MOD) return x + y - MOD;
return x + y;
}
int mult(int x, int y) {
return (int)((1ll * x * y) % MOD);
}
int subt(int x, int y) {
if(x - y < 0) return x - y + MOD;
return x - y;
}
int fp(lli x, lli y) {
lli ret = 1;
while(y > 0ll) {
if(y & 1ll) {
ret = mult(ret, x);
}
x = mult(x, x);
y /= 2ll;
}
return ret;
}
vector<bool> dp(N, 0), dpp(N, 0);
vector<vector<int> > adj(N, vector<int>());
vector<bool> dep(N, 0);
vector<int> sub(N, 0);
lli n, d;
void dfsdp(int node, int par) {
sub[node] = 1;
for(auto c : adj[node]) {
if(c == par) continue;
dep[c] = !dep[node];
dfsdp(c, node);
sub[node] += sub[c];
if(!dp[c]) dp[node] = 1;
}
}
void dfsdpp(int node, int par) {
bool f = 0;
for(auto c : adj[node]) {
if(c == par) continue;
if(!dpp[node]) dpp[c] = 1;
if(f) dpp[c] = 1;
if(!dp[c]) f = 1;
}
f = 0;
for(int i = adj[node].size() - 1; i>=0; i--) {
auto c = adj[node][i];
if(c == par) continue;
if(f) dpp[c] = 1;
if(!dp[c]) f = 1;
}
for(auto c : adj[node]) {
if(c == par) continue;
dfsdpp(c, node);
}
}
int ans = 0, win = 0;
void dfswin(int node, int par) {
int lcnt = 0;
if(!dep[node]) {
for(auto c : adj[node]) {
if(c == par) continue;
if(!dp[c]) lcnt++;
}
if(lcnt > 1) {
ans = add(ans, mult(sub[node], n));
return;
}
else {
for(auto c : adj[node]) {
if(c == par || dp[c]) continue;
ans = add(ans, mult(sub[node] - sub[c], n));
dfswin(c, node);
}
return;
}
}
else {
ans = add(ans, n - win);
for(auto c : adj[node]) {
if(c == par) continue;
dfswin(c, node);
}
}
}
void dfslose(int node, int par) {
if(!dep[node]) {
ans = add(ans, win);
for(auto c : adj[node]) {
if(c == par) continue;
dfslose(c, node);
}
}
else {
int lcnt = 0;
for(auto c : adj[node]) {
if(c == par) continue;
if(!dp[c]) lcnt++;
}
if(lcnt > 1) {
return;
}
else {
for(auto c : adj[node]) {
if(c == par || dp[c]) continue;
dfslose(c, node);
}
}
}
}
void solve() {
cin >> n >> d;
REP(i, n - 1) {
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
if(n == 2) {
cout << fp(4, d) << "\n";
return;
}
dfsdp(1, 0);
dpp[1] = 1;
dfsdpp(1, 0);
// for(int i = 1; i <= n; i++) {
// cout << "i: " << i << " dpp: " << dpp[i] << "\n";
// }
for(int i = 1; i <= n; i++) {
if(i != 1 && dpp[i] == 0) {
dpp[i] = 1;
}
else {
dpp[i] = 0;
}
for(auto c : adj[i]) {
if(!dp[c]) dpp[i] = 1;
}
win += !dpp[i];
}
for(int i = 1; i <= n; i++) {
cout << "i:" << i << " dp:" << dp[i] << " dpp:" << dpp[i] << "\n";
}
if(dpp[1]) {
dfswin(1, 0);
}
else {
dfslose(1, 0);
}
cout << ans << "\n";
}
signed main() {
fastio();
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3420 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
