UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#213610#2715. 8.4t4huangyuhe010ms1624kbC++11754b2024-11-12 21:41:092024-11-12 23:56:31

answer

#include <bits/stdc++.h>
#define C__ const
#define int long long
using namespace std;
C__ int N_ = 5010, MOD = 1e9 + 7;
int n, a[N_], b[N_];
vector<int> g[N_];
void dfs(int u, int p) {
	a[u] = 1;
	for (int v : g[u]) if (v != p) {
		dfs(v, u);
		(a[u] *= b[v]) %= MOD;
		(b[u] += b[v]) %= MOD;
	}
	(b[u] += a[u]) %= MOD;
}
void change(int u, int p) {
	for (int v : g[u]) if (v != p) {
		(a[v] *= ((b[u] - b[v]) % MOD + MOD) % MOD) %= MOD;
		change(v, u);
	}
}
signed main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, 0);
	change(1, 0);
	int ans = 0;
	for (int i = 1; i <= n; i++) (ans += a[i]) %= MOD;
	cout << ans << "\n";
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 1368kb

input:

10
1 2
1 3
3 4
3 5
3 6
3 7
1 8
5 9
5 10

output:

114

result:

wrong answer 1st numbers differ - expected: '227506.00000', found: '114.00000', error = '0.99950'

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 1368kb

input:

10
1 2
1 3
3 4
4 5
5 6
4 7
5 8
8 9
8 10

output:

712

result:

wrong answer 1st numbers differ - expected: '70140.00000', found: '712.00000', error = '0.98985'

Test #3:

score: 0
Wrong Answer
time: 0ms
memory: 1372kb

input:

100
1 2
1 3
1 4
3 5
5 6
4 7
7 8
8 9
8 10
3 11
7 12
1 13
5 14
8 15
10 16
7 17
1 18
6 19
10 20
15 21
7...

output:

285118581

result:

wrong answer 1st numbers differ - expected: '875072841.00000', found: '285118581.00000', error = '0....

Test #4:

score: 0
Wrong Answer
time: 0ms
memory: 1368kb

input:

100
1 2
2 3
3 4
4 5
4 6
6 7
5 8
8 9
8 10
1 11
6 12
4 13
9 14
13 15
7 16
3 17
15 18
17 19
9 20
8 21
4...

output:

437523147

result:

wrong answer 1st numbers differ - expected: '706867541.00000', found: '437523147.00000', error = '0....

Test #5:

score: 0
Wrong Answer
time: 0ms
memory: 1372kb

input:

100
1 2
2 3
3 4
2 5
2 6
5 7
2 8
4 9
7 10
5 11
11 12
6 13
8 14
13 15
5 16
11 17
16 18
11 19
7 20
19 2...

output:

5689489

result:

wrong answer 1st numbers differ - expected: '515055734.00000', found: '5689489.00000', error = '0.98...

Test #6:

score: 0
Wrong Answer
time: 0ms
memory: 1392kb

input:

500
1 2
1 3
3 4
3 5
5 6
1 7
3 8
8 9
4 10
6 11
7 12
2 13
11 14
8 15
7 16
9 17
2 18
3 19
15 20
2 21
20...

output:

886548347

result:

wrong answer 1st numbers differ - expected: '28964814.00000', found: '886548347.00000', error = '29....

Test #7:

score: 0
Wrong Answer
time: 0ms
memory: 1396kb

input:

500
1 2
1 3
1 4
2 5
5 6
5 7
4 8
8 9
1 10
4 11
8 12
6 13
13 14
13 15
12 16
1 17
10 18
13 19
1 20
1 21...

output:

336784187

result:

wrong answer 1st numbers differ - expected: '900482908.00000', found: '336784187.00000', error = '0....

Test #8:

score: 0
Wrong Answer
time: 3ms
memory: 1624kb

input:

5000
1 2
1 3
1 4
3 5
3 6
5 7
4 8
4 9
1 10
5 11
6 12
10 13
12 14
14 15
12 16
8 17
14 18
9 19
8 20
20 ...

output:

9716686

result:

wrong answer 1st numbers differ - expected: '255910011.00000', found: '9716686.00000', error = '0.96...

Test #9:

score: 0
Wrong Answer
time: 4ms
memory: 1624kb

input:

5000
1 2
1 3
1 4
2 5
1 6
5 7
2 8
5 9
4 10
9 11
10 12
8 13
7 14
13 15
12 16
5 17
9 18
8 19
3 20
4 21
...

output:

196789325

result:

wrong answer 1st numbers differ - expected: '506490313.00000', found: '196789325.00000', error = '0....

Test #10:

score: 0
Wrong Answer
time: 3ms
memory: 1624kb

input:

5000
1 2
1 3
1 4
4 5
4 6
3 7
2 8
8 9
6 10
9 11
3 12
3 13
7 14
13 15
4 16
10 17
9 18
10 19
5 20
17 21...

output:

970625436

result:

wrong answer 1st numbers differ - expected: '738067707.00000', found: '970625436.00000', error = '0....