Submission #3008500

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const ll MOD = (ll) (1e9 + 7);
const double PI = acos(-1.0);
const int limit = 100010;

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define NP(v) next_permutation(v.begin(),v.end())
#define debug(x) cout << #x << ":" << x << endl;
#define debug2(x) for(auto a : x) cout << a << " "; cout << endl;
#define debug3(x) rep(i, sizeof(x)) cout << x[i] << " "; cout << endl;

vector<pii> around = {MP(1, 0), MP(-1, 0), MP(0, 1), MP(0, -1)};

//------------------------------------------------------

template <typename T = ll, typename U = ll> class dijkstra {
public:

    struct edge {
        T to;
        U cost;
    };

    using P = pair<U, T>;
    map<T, vector<edge> > E;
    map<T, U> d;

    void calc(T s) {
        priority_queue <P, vector<P>, greater<P> > que;
        rep(i, limit) d[i] = LINF; //INF
        que.emplace(U(0), s);
        d[s] = U(0);
        while (!que.empty()) {
            P p = que.top();
            que.pop();
            T v = p.second;
            if (d[v] < p.first) continue;

            for (auto&& e : E[v]) {
                //if (d.find(e.to) == d.end()) d[e.to] = INF;
                if (d[e.to] > d[v] + e.cost) {
                    d[e.to] = d[v] + e.cost;
                    que.emplace(d[e.to], e.to);
                }
            }
        }
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    dijkstra<> ds;

    rep(i, n - 1) {
        ll a, b;
        cin >> a >> b;
        a--, b--;
        ds.E[a].push_back({b, 1});
        ds.E[b].push_back({a, 1});
    }
    ds.calc(0);
    priority_queue<pll> que;
    ll f[n], g[n];
    rep(i, n) que.push(MP(ds.d[i], i));

    while (!que.empty()) {
        ll depth = que.top().first;
        ll node = que.top().second;
        que.pop();
        set<ll> children;
        for (auto e : ds.E[node]) {
            if (ds.d[e.to] == depth + 1) children.insert(e.to);
        }
        f[node] = g[node] = 1;
        for (auto c : children) g[node] = g[node] * f[c] % MOD;
        for (auto c : children) f[node] = f[node] * g[c] % MOD;
        f[node] = (f[node] + g[node]) % MOD;
    }
    cout << f[0] << endl;
    return 0;
}

Submission Info

Judge Result