解法

直径を作るpathを取り出す。$O(N)$。

単純な無向木という条件から閉路はなく、ある点に$3$つ以上の区間が重なることはない。 これにより区間の絵を書くと以下のようなものになる。

A-BABA--BABABABA--------BA--BA--BABAB
 A----BA--------BABABABA--BA--BA-----B

逆にここからどういうグラフができるかを考えれば「ほとんど直線状」なもの。 次みたいな感じ。

                 * * *     * *                *   *                   *   *
                  \|/      |/                  \ /                     \ /
*--------*---------*-------*------*------*------*-----*----------*------*----*

与えられたグラフがこの形になっているかを確認し、後は葉たちの順序の組合せなどを数えればよい。 直径の端点の選択は自由であるので別のものを選んだ場合を漏らさないこと、並べる順序を左右反転した場合を忘れないことに注意。

メモ

$11$WA

実装

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
using namespace std;
template <class T> inline void chmax(T & a, T const & b) { a = max(a, b); }

template <int32_t MOD>
struct mint {
    int64_t data;  // faster than int32_t a little
    mint() = default;  // data is not initialized
    mint(int64_t value) : data(value) {}  // assume value is in proper range
    inline mint<MOD> operator + (mint<MOD> other) const { int64_t c = this->data + other.data; return mint<MOD>(c >= MOD ? c - MOD : c); }
    inline mint<MOD> operator - (mint<MOD> other) const { int64_t c = this->data - other.data; return mint<MOD>(c <    0 ? c + MOD : c); }
    inline mint<MOD> operator * (mint<MOD> other) const { int64_t c = this->data * int64_t(other.data) % MOD; return mint<MOD>(c < 0 ? c + MOD : c); }
    inline mint<MOD> & operator += (mint<MOD> other) { this->data += other.data; if (this->data >= MOD) this->data -= MOD; return *this; }
    inline mint<MOD> & operator -= (mint<MOD> other) { this->data -= other.data; if (this->data <    0) this->data += MOD; return *this; }
    inline mint<MOD> & operator *= (mint<MOD> other) { this->data = this->data * int64_t(other.data) % MOD; if (this->data < 0) this->data += MOD; return *this; }
};

template <int32_t MOD>
mint<MOD> fact(int n) {
    static vector<mint<MOD> > memo(1, 1);
    while (n >= memo.size()) {
        memo.push_back(memo.back() * mint<MOD>(memo.size()));
    }
    return memo[n];
}

pair<int, int> get_eccentricity(int k, vector<vector<int> > const & tree) {
    pair<int, int> result = { -1, -1 };  // (depth, vertex)
    function<void (int, int, int)> dfs = [&](int i, int parent, int depth) {
        chmax(result, make_pair(depth, i));
        for (int j : tree[i]) if (j != parent) {
            dfs(j, i, depth + 1);
        }
    };
    dfs(k, -1, 0);
    return result;
}
int get_diameter(vector<vector<int> > const & tree) {
    return get_eccentricity(get_eccentricity(0, tree).second, tree).first;
}

constexpr int MOD = 1e9 + 7;

mint<MOD> solve(int n, vector<vector<int> > const & g) {
    // check the constructivity
    int t1 = get_eccentricity(0,  g).second;
    int t2 = get_eccentricity(t1, g).second;
    assert (g[t1].size() == 1);
    assert (g[t2].size() == 1);
    vector<int> leaves;
    for (int i = g[t1][0], parent = -1; i != t2; ) {
        assert (g[i].size() >= 2);
        leaves.push_back(g[i].size() - 2);  // push the number of leaves

        int next = -1;
        for (int j : g[i]) if (j != parent) {
            if (g[j].size() >= 2 or j == t2) {  // if a non-leaf exists
                if (next != -1) return 0;
                next = j;  // goto the unique non-leaf
            }
        }
        assert (next != -1);
        parent = i;
        i = next;
    }

    // count
    if (leaves.empty()) {  // the graph with two nodes
        return 4;
    } else {
        leaves.front() += 1;  // for t1
        leaves.back()  += 1;  // for t2

        mint<MOD> cnt = 1;
        for (int l : leaves) {
            cnt *= fact<MOD>(l);
        }
        if (leaves.size() >= 2) {
            cnt *= 2;  // flip
        }
        cnt *= 4;  // t1, t2
        return cnt;
    }
}

int main() {
    // input
    int n; cin >> n;
    vector<vector<int> > g(n);
    REP (i, n - 1) {
        int u, v; cin >> u >> v;
        -- u;
        -- v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // solve
    auto cnt = solve(n, g);

    // output
    cout << cnt.data << endl;
    return 0;
}