結果
| 問題 |
No.828 全方位神童数
|
| コンテスト | |
| ユーザー |
 polyomino_24
|
| 提出日時 | 2019-05-04 00:39:59 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 193 ms / 2,000 ms |
| コード長 | 6,382 bytes |
| コンパイル時間 | 1,528 ms |
| コンパイル使用メモリ | 130,740 KB |
| 最終ジャッジ日時 | 2025-01-07 03:34:53 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 43 |
ソースコード
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> a) {
os << '(' << a.first << ',' << a.second << ')';
return os;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> v) {
for (auto x : v) os << x << ' ';
return os;
}
void debug() {
cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
cerr << a;
if (sizeof...(b)) cerr << ", ";
debug(b...);
}
template<int MOD>
class modint{
public:
int a;
modint(const long long v = 0):a(v % MOD){}
int getmod() const{
return MOD;
}
modint operator+(const modint rhs) const{
return modint(*this) += rhs;
}
modint operator-(const modint rhs) const{
return modint(*this) -= rhs;
}
modint operator*(const modint rhs) const{
return modint(*this) *= rhs;
}
modint operator/(const modint rhs) const{
return modint(*this) /= rhs;
}
modint operator+(const long long rhs) const{
return modint(*this) += rhs;
}
modint operator-(const long long rhs) const{
return modint(*this) -= rhs;
}
modint operator*(const long long rhs) const{
return modint(*this) *= rhs;
}
modint operator/(const long long rhs) const{
return modint(*this) /= rhs;
}
friend modint operator+(const long long a, const modint b){
return b + a;
}
friend modint operator-(const long long a, const modint b){
return -b + a;
}
friend modint operator*(const long long a, const modint b){
return b * a;
}
friend modint operator/(const long long a, const modint b){
return modint(a) / b;
}
modint &operator+=(const modint rhs){
a += rhs.a;
if(a >= MOD){
a -= MOD;
}
return *this;
}
modint &operator-=(const modint rhs){
if(a < rhs.a){
a += MOD;
}
a -= rhs.a;
return *this;
}
modint &operator*=(const modint rhs){
a = (long long)a * rhs.a % MOD;
return *this;
}
modint &operator/=(modint rhs){
int x = MOD - 2;
while(x){
if(x % 2){
*this *= rhs;
}
rhs *= rhs;
x /= 2;
}
return *this;
}
modint &operator++(){
*this += 1;
return *this;
}
modint &operator--(){
*this -= 1;
return *this;
}
modint operator++(int){
modint res = *this;
++(*this);
return res;
}
modint operator--(int){
modint res = *this;
res -= 1;
return res;
}
modint &operator+=(const long long rhs){
*this += modint(rhs);
return *this;
}
modint &operator-=(const long long rhs){
*this -= modint(rhs);
return *this;
}
modint &operator*=(const long long rhs){
*this *= modint(rhs);
return *this;
}
modint &operator/=(const long long rhs){
*this /= modint(rhs);
return *this;
}
modint operator+() const{
return *this;
}
modint operator-() const{
return modint()-*this;
}
bool operator==(const modint rhs) const{
return a == rhs.a;
}
bool operator==(const long long rhs) const{
return a == rhs;
}
friend bool operator==(const long long a, const modint b){
return a == b.a;
}
bool operator!=(const modint rhs) const{
return a != rhs.a;
}
bool operator!=(const long long rhs) const{
return a != rhs;
}
friend ostream &operator<<(ostream &os, const modint x){
os << x.a;
return os;
}
friend istream &operator>>(istream &is, modint &x){
is >> x.a;
return is;
}
explicit operator bool() const{
return a > 0;
}
bool operator!(){
return a == 0;
}
explicit operator int() const{
return a;
}
explicit operator long long() const{
return (long long) a;
}
friend modint pow(modint a, long long b){
modint res = 1;
while(b){
if(b % 2){
res *= a;
}
a *= a;
b /= 2;
}
return res;
}
};
using mint = modint<1000000007>;
vector<int>g[200005];
int par[200005];
int sz[200005];
int b[200005];
int gya[200005];
mint r[200005];
vector<vector<int>>d;
int find(int x){
if(par[x] == x)return x;
else return par[x] = find(par[x]);
}
void unite(int x,int y){
x = find(x);
y = find(y);
if(x == y)return;
if(sz[x] >= sz[y]){
for(auto z:d[y]){
d[x].push_back(z);
}
sz[x] += sz[y];
par[y] = x;
}else{
swap(x,y);
for(auto z:d[y]){
d[x].push_back(z);
}
sz[x] += sz[y];
par[y] = x;
}
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin >> n;
rep(i,n)cin >> r[i];
d.resize(n);
rep(i,n){
sz[i] = 1;
par[i] = i;
d[i].emplace_back(i);
}
rep(i,n-1){
int a,b;
cin >> a >> b;
a--,b--;
if(b > a)swap(a,b);
g[a].push_back(b);
}
vector<pii>p;
rep(i,n){
for(auto x: g[i]){
unite(i,x);
}
int t = find(i);
show(i,t);
p.emplace_back(d[t][0],d[t].back());
}
int t = find(0);
rep(i,n){
gya[d[t][i]] = i;
}
for(auto &x : p){
b[gya[x.first]]++;
b[gya[x.second]+1]--;
}
rep(i,n)b[i+1] += b[i];
mint ans = 1;
rep(i,n){
ans *= (r[i] + b[gya[i]]);
}
cout << ans << endl;
}