tdpcn.cpp

    #include <cstdio>
    #include <vector>
    #include <algorithm>
    using namespace std;
    typedef long long lint;
    typedef pair<lint,int> pi;
    const int mod = 1e9 + 7;
     
    int bino[1005][1005];
    int n;
    vector<int> graph[1005];
     
    int sz[1005], par[1005];
     
    int dfs(int x, int pa){
        sz[x] = 1;
        par[x] = pa;
        for (int i=0; i<graph[x].size(); i++) {
            if(graph[x][i] == pa) continue;
            sz[x] += dfs(graph[x][i],x);
        }
        return sz[x];
    }
     
    pi s(int x, int pa){
        vector<int> v;
        lint ret = 1;
        int sub = 0, tsub = 0;
        for (int i=0; i<graph[x].size(); i++) {
            if(graph[x][i] == pa) continue;
            pi t = s(graph[x][i],x);
            ret *= t.first;
            sub += t.second;
            ret %= mod;
            v.push_back(t.second);
        }
        tsub = sub;
        for (int i=0; i<v.size(); i++) {
            ret *= bino[tsub][v[i]];
            ret %= mod;
            tsub -= v[i];
        }
        return pi(ret,sub+1);
    }
     
    int main(){
        scanf("%d",&n);
        for (int i=0; i<=n; i++) {
            bino[i][0] = 1;
            for (int j=1; j<=i; j++) {
                bino[i][j] = bino[i-1][j] + bino[i-1][j-1];
                bino[i][j] %= mod;
            }
        }
        for (int i=0; i<n-1; i++) {
            int u,v;
            scanf("%d %d",&u,&v);
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        dfs(1,0);
        int ret = 0;
        for (int i=2; i<=n; i++) {
            lint tmp = s(i,par[i]).first * bino[n-2][sz[i] - 1] % mod;
            tmp *= s(par[i],i).first;
            tmp %= mod;
            ret += tmp;
            ret %= mod;
        }
        printf("%d\n",ret);
    }