Submission #5541998


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};


vector<LL> fact;
vector<LL> inver(200001);
vector<int> v[1001];

LL combi(int n,int r){
    if(n<r||n<0||r<0) return 0;
    return fact[n]%mod*inver[n-r]%mod*inver[r]%mod;
}
 
 
LL fpow(LL a, LL n){
    LL x = 1;
    while(n > 0){
        if(n&1){
            x=x*a%mod;
        }
        a=a*a%mod;
        n >>= 1;
    }
    return x;
}
 
void set_combi(){
    LL s=1;
    fact.push_back(1);
    for(int i=1;i<=200000;i++){
        s*=i;
        s%=mod;
        fact.push_back(s);
    }
    inver[200000]=fpow(fact[200000],mod-2);
    for(int i=199999;i>=0;i--){
        inver[i]=inver[i+1]*(i+1)%mod;
    }
}

 
P dfs(int u,int k,int l){
    P ret = mp(1,0);
    for (int i = 0; i < v[u].size(); i++) {
        if(v[u][i]==k) continue;
        P p = dfs(v[u][i],u,l);
        ret.sc += p.sc;
        ret.fs = ret.fs*combi(ret.sc,p.sc)%mod*p.fs%mod;
    }
    ret.sc++;
    return ret;
}



int main(){
    set_combi();
    int n;cin >> n;
    for (int i = 0; i < n-1; i++) {
        int x,y;cin >> x >> y;
        x--,y--;
        v[x].pb(y);
        v[y].pb(x);
    }
    LL ans = 0;
    for (int i = 0; i < n; i++) {
        ans = (ans + dfs(i,-1,i).fs)%mod;
    }
    cout << ans*inver[2]%mod << endl;
    return 0;
}

Submission Info

Submission Time
Task N - 木
User Yukly
Language C++14 (GCC 5.4.1)
Score 5
Code Size 1682 Byte
Status AC
Exec Time 34 ms
Memory 4980 KB

Judge Result

Set Name All
Score / Max Score 5 / 5
Status
AC × 9
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 90, 91
Case Name Status Exec Time Memory
00 AC 34 ms 3956 KB
01 AC 25 ms 3956 KB
02 AC 28 ms 3956 KB
03 AC 28 ms 3956 KB
04 AC 28 ms 4980 KB
05 AC 28 ms 3956 KB
06 AC 28 ms 3956 KB
90 AC 6 ms 3956 KB
91 AC 6 ms 3956 KB