#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<long double, long double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ld long double
#define pmax pair<__int128, __int128>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]= {0, 1, 0, -1}, dy[4]= {1, 0, -1, 0};
int ddx[8]={1, 1, 0, -1, -1, -1, 0, 1}, ddy[8]={0, 1, 1, 1, 0, -1, -1, -1};
const int mxN=100025;
const int mxM=300005;
const int mxK=1000000000;
const ll MOD=1000'000'007;
const ll INF=1000000000000000005;
ll N, D;
vector <int> v[mxN];
ll outw[mxN];
ll downw[mxN], upw[mxN];
bool W[mxN];
ll degL[mxN];
vector <int> v1[mxN], v2[mxN];
ll sizw1[mxN], leafw2[mxN], sizl2[mxN], par1[mxN], par2[mxN];
ll numw;
void dfs_downw(int now, int pre)
{
for(int nxt : v[now]) if(nxt!=pre)
{
dfs_downw(nxt, now);
}
downw[now]=(outw[now]==0 ? 1 : 0);
if(now!=1) outw[pre]+=downw[now];
}
void dfs_upw(int now, int pre)
{
if(now!=1)
{
upw[now]=(outw[pre]-downw[now]==0 ? 1 : 0);
outw[now]+=upw[now];
}
for(int nxt : v[now]) if(nxt!=pre)
{
dfs_upw(nxt, now);
}
}
int findpar(int a, int typ)
{
if(typ==1) return (par1[a]==a ? a : par1[a]=findpar(par1[a], 1));
else return (par2[a]==a ? a : par2[a]=findpar(par2[a], 2));
}
void onion(int a, int b, int typ)
{
int p=findpar(a, typ), q=findpar(b, typ);
if(typ==1)
{
par1[p]=q; sizw1[q]+=sizw1[p];
}
else
{
par2[p]=q; sizl2[q]+=sizl2[p]; leafw2[q]+=leafw2[p];
}
}
int main()
{
gibon
cin >> N >> D;
for(int i=1;i<N;i++)
{
int a, b; cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs_downw(1, -1);
dfs_upw(1, -1);
for(int i=1;i<=N;i++)
{
W[i]=(outw[i]>=1);
numw+=W[i];
}
for(int i=1;i<=N;i++)
{
for(int ele : v[i])
{
if(!W[ele]) degL[i]++;
}
}
for(int i=1;i<=N;i++)
{
if(!W[i] || degL[i]) continue;
for(int ele : v[i]) if(W[ele] && degL[ele]==0) v1[i].push_back(ele);
}
for(int i=1;i<=N;i++)
{
if(!W[i])
{
for(int ele : v[i]) if(degL[ele]<3) v2[i].push_back(ele);
}
else if(degL[i]<3)
{
for(int ele : v[i]) if(!W[ele]) v2[i].push_back(ele);
}
}
for(int i=1;i<=N;i++)
{
par1[i]=par2[i]=i;
if(degL[i]==0 && W[i]) sizw1[i]=1;
if(v2[i].size()==1 && W[i]) leafw2[i]=1;
if(!W[i]) sizl2[i]=1;
}
for(int i=1;i<=N;i++)
{
for(int ele : v1[i]) if(ele<i)
{
onion(ele, i, 1);
}
for(int ele : v2[i]) if(ele<i)
{
onion(ele, i, 2);
}
}
if(W[1])
{
ll ans=N*N;
if(degL[1]==0) ans-=(N-numw)*(sizw1[findpar(1, 1)]/2);
if(degL[1]<3 && degL[1]>0 && v2[1].size()==1) ans-=(N-numw)*sizl2[findpar(1, 2)];
cout << ans%MOD;
}
else
{
ll ans=0;
ans+=(N-numw)*sizl2[findpar(1, 2)];
cout << ans%MOD;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
7508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
7380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
7380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
7380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
7380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
7380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
7508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
