#include <bits/stdc++.h>
#define C 1
#define P 0
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
const ll NMAX = 100001;
const ll VMAX = 101;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 447;
const ll base = 117;
const ll nr_of_bits = 18;
const ll inv2 = 500000004;
vector <ll> v[NMAX];
ll col[NMAX];
ll children[NMAX][2];
ll maximal[NMAX];
ll rosii[NMAX];
ll criticals[NMAX];
ll adv[NMAX];
ll sumR[NMAX][2];
void DFS(ll node, ll p){
col[node] = P;
for(auto x : v[node]){
if(x == p) continue;
DFS(x, node);
children[node][col[x]]++;
}
if(children[node][C] == (ll)v[node].size() - (p != 0)){
col[node] = P;
}else{
col[node] = C;
}
if(col[node] == P)
rosii[node] = 1;
for(auto x : v[node]){
if(x == p) continue;
if(col[node] != col[x] && children[node][C] >= (ll)v[node].size() - (p != 0) - 1){
rosii[node] += rosii[x];
}
sumR[node][col[x]] += rosii[x];
}
}
ll perdanti = 0;
void bagaR(int node, int p){
rosii[node] = (col[node] == P);
if(children[node][C] >= (ll)v[node].size() - (p != 0) - 1) { /// mereu facem bagaR pentru root
rosii[node] += sumR[node][P + C - col[node]];
}
}
void Rerooting(ll node, ll p){
adv[node] = col[node];
criticals[node] = rosii[node];
if(adv[node] == P)
perdanti++;
for(auto x : v[node]){
if(x == p) continue;
ll cx = col[x], cnode = col[node];
children[node][col[x]]--;
sumR[node][col[x]] -= rosii[x];
if(children[node][C] == v[node].size() - 1){
col[node] = P;
}else{
col[node] = C;
}
bagaR(node, x);
children[x][col[node]]++;
sumR[x][col[node]] += rosii[node];
if(children[x][C] == v[x].size()){
col[x] = P;
}else{
col[x] = C;
}
bagaR(x, 0);
Rerooting(x, node);
children[x][col[node]]--;
sumR[x][col[node]] -= rosii[node];
col[x] = cx;
bagaR(x, node);
col[node] = cnode;
children[node][col[x]]++;
sumR[node][col[x]] += rosii[x];
bagaR(node, 0);
}
}
ll lgput(ll n, ll p){
ll r = 1;
while(p){
if(p % 2){
r *= n;
r %= MOD;
}
n *= n;
n %= MOD;
p /= 2;
}
return r;
}
void add(ll &x, ll val){
x += val;
if(x >= MOD)
x -= MOD;
if(x < 0)
x += MOD;
}
ll L[NMAX];
int main() {
ifstream cin(".in");
ofstream cout(".out");
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n, d, i, criticalDif = 0;
cin >> n >> d;
if(n == 2){
cout << lgput(4, d);
return 0;
}
for(i = 1; i < n; i++){
ll a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
DFS(2, 0);
Rerooting(2, 0);
for(i = 1; i <= n; i++){
if(adv[i] == P){
add(criticalDif, -criticals[i]);
}else{
add(criticalDif, criticals[i]);
}
}
ll B = criticalDif;
ll A = (perdanti * n) % MOD * n % MOD;
/// L0 = perdanti
/// L1 = A + L0 * B
/// Li = A + Li-1 * B
L[0] = perdanti;
for(i = 1; i <= d - 1; i++){
L[i] = ((lgput(n, 2 * i) % MOD * perdanti) % MOD + (L[i - 1] * B) % MOD) % MOD;
}
ll schimba = (L[d - 1] * criticals[1]) % MOD;
if(adv[1] == P){
cout << schimba;
}else{
cout << (lgput(n, 2 * d) % MOD - schimba + MOD) % MOD;
}
return 0;
}
Compilation message
startrek.cpp: In function 'void Rerooting(ll, ll)':
startrek.cpp:72:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | if(children[node][C] == v[node].size() - 1){
| ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
startrek.cpp:80:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | if(children[x][C] == v[x].size()){
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
startrek.cpp: In function 'int main()':
startrek.cpp:150:8: warning: unused variable 'A' [-Wunused-variable]
150 | ll A = (perdanti * n) % MOD * n % MOD;
| ^
| # |
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 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
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 |
- |
