Submission #1535384
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
//#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
const ll mod = 1000000000 + 7;
const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;
int n;
vector<vector<int>> g(100000 + 5);
pair<ll, ll> dfs(int now, int par) {
pair<ll, ll> ret;
ll wcnt = 1;
ll bcnt = 1;
for (auto to : g[now]) {
if (to == par) continue;
pair<ll, ll> tmp = dfs(to, now);
(wcnt *= (tmp.fi + tmp.se)) %= mod;
(bcnt *= tmp.fi)%= mod;
}
ret = make_pair(wcnt, bcnt);
return ret;
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n;
rep(i, n - 1) {
int a, b;
cin >> a >> b;
a--; b--;
g[a].push_back(b);
g[b].push_back(a);
}
pair<ll, ll> ans = dfs(0, -1);
cout << (ans.fi + ans.se) % mod << endl;
}
Submission Info
Submission Time |
|
Task |
D - 塗り絵 |
User |
roto_37 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1780 Byte |
Status |
AC |
Exec Time |
38 ms |
Memory |
5760 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt |
Case Name |
Status |
Exec Time |
Memory |
000.txt |
AC |
2 ms |
2560 KB |
001.txt |
AC |
2 ms |
2560 KB |
002.txt |
AC |
29 ms |
5120 KB |
003.txt |
AC |
38 ms |
5760 KB |
004.txt |
AC |
25 ms |
4736 KB |
005.txt |
AC |
37 ms |
5760 KB |
006.txt |
AC |
34 ms |
5504 KB |
007.txt |
AC |
37 ms |
5760 KB |
008.txt |
AC |
32 ms |
4864 KB |
009.txt |
AC |
37 ms |
5760 KB |
010.txt |
AC |
27 ms |
4864 KB |
011.txt |
AC |
37 ms |
5760 KB |
012.txt |
AC |
22 ms |
4480 KB |
013.txt |
AC |
37 ms |
5760 KB |
014.txt |
AC |
17 ms |
4096 KB |
015.txt |
AC |
35 ms |
5760 KB |
016.txt |
AC |
23 ms |
4608 KB |
017.txt |
AC |
35 ms |
5760 KB |
018.txt |
AC |
8 ms |
3200 KB |
019.txt |
AC |
38 ms |
5760 KB |
020.txt |
AC |
5 ms |
2944 KB |
021.txt |
AC |
37 ms |
5760 KB |