Submission #1132561
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
const int md = 1000000007;
inline void add(int &a, int b) {
a += b;
if (a >= md) {
a -= md;
}
}
inline int mul(int a, int b) {
return (long long) a * b % md;
}
const int N = 2010;
int depth[N];
vector <int> g[N], new_g[N];
int it, mark[N][N];
int f[N][N];
int D;
int go(int v, int pr, int x) {
if (mark[v][x] == it) {
return f[v][x];
}
mark[v][x] = it;
f[v][x] = 1;
int y = (D - depth[v]) - x;
// cerr << "go " << v << " " << x << " " << y << endl;
int sz = g[v].size();
for (int j = 0; j < sz; j++) {
int u = g[v][j];
if (u == pr) {
continue;
}
int cur = 0;
if (x > 0) {
cur = go(u, v, x - 1);
}
if (y > 0) {
add(cur, go(u, v, x));
}
f[v][x] = mul(f[v][x], cur);
}
return f[v][x];
}
int curr[N][N];
int x[N], d[N];
int C[N][N];
pair <int, int> edge[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n - 1; i++) {
int foo, bar;
scanf("%d %d", &foo, &bar);
foo--; bar--;
edge[i] = make_pair(foo, bar);
g[foo].push_back(bar);
g[bar].push_back(foo);
}
int max_deg = 0;
for (int i = 0; i < n; i++) {
max_deg = max(max_deg, (int) g[i].size());
}
if (max_deg <= 2) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (j == 0) C[i][j] = 1; else
if (i == 0) C[i][j] = 0;
else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % md;
}
}
int ans = C[n - 1][(n - 1) / 2];
if (n % 2 == 0) {
add(ans, ans);
}
printf("%d\n", ans);
return 0;
}
int coeff = 1;
int root;
int another_root;
int diam = 0;
while (true) {
D = (int) 1e9;
root = -1;
another_root = -1;
for (int start = 0; start < n; start++) {
for (int i = 0; i < n; i++) {
d[i] = -1;
}
int b = 0, e = 1;
x[0] = start;
d[start] = 0;
while (b < e) {
int sz = g[x[b]].size();
for (int j = 0; j < sz; j++) {
int u = g[x[b]][j];
if (d[u] == -1) {
x[e] = u;
d[u] = d[x[b]] + 1;
e++;
}
}
b++;
}
int rad = 0;
for (int i = 0; i < n; i++) {
rad = max(rad, d[i]);
}
diam = max(diam, rad);
if (rad < D) {
D = rad;
root = start;
another_root = -1;
for (int i = 0; i < n; i++) {
depth[i] = d[i];
}
} else {
if (rad == D) {
another_root = start;
}
}
}
if (diam % 2 == 0) {
break;
}
coeff = mul(coeff, 2);
break;
/* assert(another_root != -1);
for (int i = 0; i < n - 1; i++) {
new_g[i].clear();
}
for (int i = 0; i < n - 1; i++) {
int foo = edge[i].first;
int bar = edge[i].second;
if (foo == another_root) {
foo = root;
}
if (bar == another_root) {
bar = root;
}
if (foo == n - 1) {
foo = another_root;
}
if (bar == n - 1) {
bar = another_root;
}
new_g[foo].push_back(bar);
new_g[bar].push_back(foo);
}
n--;
for (int i = 0; i < n; i++) {
g[i] = new_g[i];
}*/
}
// cerr << "D = " << D << endl;
// cerr << "diam = " << diam << endl;
// cerr << "root = " << root << endl;
// cerr << "another_root = " << another_root << endl;
int ans = 0;
if (diam % 2 == 0) {
it = 0;
for (int x = 0; x <= D; x++) {
it++;
int cur = go(root, another_root, x);
add(ans, cur);
}
} else {
it = 0;
for (int x = 0; x <= D; x++) {
for (int y = 0; x + y <= D; y++) {
if (x + y < D - 1) {
continue;
}
it++;
bool flag = false;
if (x + y < D) {
D--;
flag = true;
}
D++;
int cur = go(another_root, root, x);
curr[x][y] = cur;
D--;
if (flag) {
D++;
} else {
if (x > 0) {
add(cur, md - curr[x - 1][y]);
}
if (y > 0) {
add(cur, md - curr[x][y - 1]);
}
}
// cerr << "now cur = " << cur << endl;
int new_x = x + 1;
int new_y = y;
int bound_x = D - new_y;
int bound_y = D - new_x;
int new_D = bound_x + bound_y;
int old_D = D;
D = new_D;
cur = mul(cur, go(root, another_root, bound_x));
add(ans, cur);
D = old_D;
// cerr << x << " " << y << " -> " << cur << endl;
}
}
}
printf("%d\n", mul(ans, coeff));
// cerr << clock() << " ms" << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Oriented Tree |
User |
tourist |
Language |
C++14 (GCC 5.4.1) |
Score |
1800 |
Code Size |
4890 Byte |
Status |
AC |
Exec Time |
943 ms |
Memory |
22912 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:59:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:62:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &foo, &bar);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1800 / 1800 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
2 ms |
6528 KB |
0_01.txt |
AC |
13 ms |
16768 KB |
0_02.txt |
AC |
2 ms |
6528 KB |
0_03.txt |
AC |
2 ms |
6528 KB |
1_00.txt |
AC |
13 ms |
16768 KB |
1_01.txt |
AC |
14 ms |
16768 KB |
1_02.txt |
AC |
14 ms |
16768 KB |
1_03.txt |
AC |
11 ms |
20864 KB |
1_04.txt |
AC |
11 ms |
20864 KB |
1_05.txt |
AC |
19 ms |
20864 KB |
1_06.txt |
AC |
23 ms |
20864 KB |
1_07.txt |
AC |
22 ms |
20864 KB |
1_08.txt |
AC |
28 ms |
20864 KB |
1_09.txt |
AC |
39 ms |
20864 KB |
1_10.txt |
AC |
41 ms |
20864 KB |
1_11.txt |
AC |
99 ms |
22912 KB |
1_12.txt |
AC |
105 ms |
20864 KB |
1_13.txt |
AC |
456 ms |
22912 KB |
1_14.txt |
AC |
419 ms |
20864 KB |
1_15.txt |
AC |
711 ms |
20864 KB |
1_16.txt |
AC |
943 ms |
20864 KB |
1_17.txt |
AC |
18 ms |
20864 KB |
1_18.txt |
AC |
16 ms |
20864 KB |
1_19.txt |
AC |
18 ms |
20864 KB |
1_20.txt |
AC |
16 ms |
20864 KB |
1_21.txt |
AC |
16 ms |
20864 KB |
1_22.txt |
AC |
14 ms |
20864 KB |
1_23.txt |
AC |
13 ms |
20864 KB |
1_24.txt |
AC |
13 ms |
20864 KB |
1_25.txt |
AC |
12 ms |
20864 KB |
1_26.txt |
AC |
12 ms |
20864 KB |
1_27.txt |
AC |
12 ms |
20864 KB |
1_28.txt |
AC |
11 ms |
20864 KB |