#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];
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 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++) if(outw[i]>=1) numw++;
int ans=0;
bool ok=outw[1]>=1;
for(int i=1;i<=N;i++)
{
if(ok) ans+=numw;
v[N+1].clear();
v[N+1].push_back(i);
v[i].push_back(N+1);
for(int i=1;i<=N+1;i++) downw[i]=upw[i]=outw[i]=0;
dfs_downw(1, -1);
dfs_upw(1, -1);
if(outw[1]>=1) ans+=N-numw;
v[i].pop_back();
}
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Incorrect |
33 ms |
2744 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 |
1 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 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
35 ms |
2644 KB |
Output is correct |
8 |
Correct |
39 ms |
2772 KB |
Output is correct |
9 |
Correct |
27 ms |
2736 KB |
Output is correct |
10 |
Correct |
37 ms |
2752 KB |
Output is correct |
11 |
Correct |
34 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
35 ms |
2644 KB |
Output is correct |
8 |
Correct |
39 ms |
2772 KB |
Output is correct |
9 |
Correct |
27 ms |
2736 KB |
Output is correct |
10 |
Correct |
37 ms |
2752 KB |
Output is correct |
11 |
Correct |
34 ms |
2644 KB |
Output is correct |
12 |
Execution timed out |
1086 ms |
10700 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
35 ms |
2644 KB |
Output is correct |
8 |
Correct |
39 ms |
2772 KB |
Output is correct |
9 |
Correct |
27 ms |
2736 KB |
Output is correct |
10 |
Correct |
37 ms |
2752 KB |
Output is correct |
11 |
Correct |
34 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Incorrect |
30 ms |
2644 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
35 ms |
2644 KB |
Output is correct |
8 |
Correct |
39 ms |
2772 KB |
Output is correct |
9 |
Correct |
27 ms |
2736 KB |
Output is correct |
10 |
Correct |
37 ms |
2752 KB |
Output is correct |
11 |
Correct |
34 ms |
2644 KB |
Output is correct |
12 |
Execution timed out |
1086 ms |
10700 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Incorrect |
33 ms |
2744 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |