Submission #5543200
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; } } vector<P> dp1(1001); vector<P> dp2(1001); int n; P dfs(int u,int prev){ dp[u] = mp(1,0); for (int i = 0; i < v[u].size(); i++) { if(v[u][i]==prev) continue; P p = dfs(v[u][i],u); dp[u].sc += p.sc; dp[u].fs = dp[u].fs*combi(dp[u].sc,p.sc)%mod*p.fs%mod; } dp[u].sc++; return dp1[u]; } void dfs2(int u,int prev,LL st,LL t){ dp2[u] = mp(st,t); for (int i = 0; i < v[u].size(); i++) { if(v[u][i]==prev) continue; dp2[u].sc += dp1[v[u][i]].sc; dp2[u].fs = dp2[u].fs*combi(dp2[u].sc,dp1[v[u][i]].sc)%mod*dp1[v[u][i]].fs%mod; } for (int i = 0; i < v[u].size(); i++) { if(v[u][i]==prev) continue; dfs2(v[u][i],u,dp2[u].fs*fpow(dp1[v[u][i]].fs*combi(dp2[u].sc,dp1[v[u][i]].sc)%mod,mod-2)%mod,n-dp1[v[u][i]].sc); } } int main(){ set_combi(); 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); } dfs(0,-1); dfs2(0,-1,1,0); LL ans = 0; for (int i = 0; i < n; i++) { ans = (ans + dp2[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 | 0 |
Code Size | 2270 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘P dfs(int, int)’: ./Main.cpp:61:5: error: ‘dp’ was not declared in this scope dp[u] = mp(1,0); ^