結果

問題 No.1507 Road Blocked
ユーザー srjywrdnprktsrjywrdnprkt
提出日時 2023-06-18 22:48:59
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 131 ms / 2,000 ms
コード長 5,495 bytes
コンパイル時間 2,530 ms
コンパイル使用メモリ 209,556 KB
実行使用メモリ 20,104 KB
最終ジャッジ日時 2023-09-08 16:35:50
合計ジャッジ時間 10,380 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 81 ms
20,104 KB
testcase_04 AC 126 ms
17,200 KB
testcase_05 AC 130 ms
17,052 KB
testcase_06 AC 129 ms
16,984 KB
testcase_07 AC 129 ms
17,100 KB
testcase_08 AC 127 ms
17,052 KB
testcase_09 AC 125 ms
16,940 KB
testcase_10 AC 127 ms
17,136 KB
testcase_11 AC 126 ms
17,180 KB
testcase_12 AC 126 ms
17,032 KB
testcase_13 AC 129 ms
17,032 KB
testcase_14 AC 124 ms
17,000 KB
testcase_15 AC 125 ms
17,128 KB
testcase_16 AC 131 ms
17,092 KB
testcase_17 AC 129 ms
16,984 KB
testcase_18 AC 126 ms
17,200 KB
testcase_19 AC 123 ms
16,916 KB
testcase_20 AC 122 ms
16,920 KB
testcase_21 AC 124 ms
16,984 KB
testcase_22 AC 124 ms
16,964 KB
testcase_23 AC 128 ms
17,108 KB
testcase_24 AC 126 ms
16,976 KB
testcase_25 AC 125 ms
17,200 KB
testcase_26 AC 123 ms
16,960 KB
testcase_27 AC 124 ms
17,036 KB
testcase_28 AC 124 ms
17,004 KB
testcase_29 AC 130 ms
17,032 KB
testcase_30 AC 126 ms
17,092 KB
testcase_31 AC 124 ms
17,128 KB
testcase_32 AC 129 ms
16,972 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

template<typename S> struct Tree{
    vector<vector<S>> E, par0;
    vector<S> dist0;
    S N, log=0;

    Tree (const vector<vector<S>> &_E){
        N = _E.size(); E = _E;
    }

    //fromを根とする木の各頂点の深さを求める
    vector<S> depth (S from) {
        vector<S> dist(N);
        _depth(from, -1, dist);
        return dist;
    }

    void _depth(S from, S p, vector<S> &dist) {
        for (auto to : E[from]){
            if (to == p) continue;
            dist[to] = dist[from]+1;
            _depth(to, from, dist);
        }
    }

    //木の二頂点(a, b)間の最短距離を求める
    S dist(S a, S b){
        S c = lca(a, b);
        return dist0[a] + dist0[b]- 2*dist0[c];
    }

    //木の二頂点(a, b)のLCAを求める
    S lca(S a, S b){
        if (par0.size() == 0){
            dist0 = depth(0);
            _doubling();
        }
        if (dist0[a] < dist0[b]) swap(a, b);
        for (S i=0; i<=log; i++){
            if ((dist0[a]-dist0[b]) & (1LL<<i)) a = par0[i][a];
        }

        if (a == b) return a;
        for (S i=log; i>=0; i--){
            if (par0[i][a] != par0[i][b]){
                a = par0[i][a];
                b = par0[i][b];
            }
        }
        
        return par0[0][a];
    }

    void _doubling(){
        S cnt = 1;
        while(cnt < N){
            cnt *= 2;
            log++;
        }
        par0.resize(log+1, vector<S>(N));
        _ancestor(0, -1);
        for (S i=1; i<=log; i++){
            for (S j=0; j<N; j++){
                if (par0[i-1][j] == -1) par0[i][j] = -1;
                else par0[i][j] = par0[i-1][par0[i-1][j]];
            }
        }
    }

    void _ancestor(S from, S p){
        par0[0][from] = p;
        for (auto to : E[from]){
            if (to == p) continue;
            _ancestor(to, from);
        }
    }

    //fromとgoalの最短経路上に含まれる点を全て求める
    vector<S> shortest_path(S from, S goal) const{
        vector<S> path, pt;
        _shortest_path(from, goal, -1, pt, path);
        return path;
    }

    void _shortest_path(S from, S goal, S p, vector<S> &pt, vector<S> &path) const{ 
        pt.push_back(from);

        if (from == goal) path = pt; 

        for (auto to : E[from]){
            if (to == p) continue;
            _shortest_path(to, goal, from, pt, path);
        }   
        pt.pop_back();
    }

    //木の直径とその両端の点を求める
    tuple<S, S, S> diameter() const{
        S s=0, t=0, mx=0;
        _diameter(s, -1, 0, mx, t); 
        s=t; t=0; mx=0;
        _diameter(s, -1, 0, mx, t); 
        return make_tuple(s, t, mx);
    }

    void _diameter(S from, S p, S d, S &mx, S &argmx) const{
        if (d > mx){
            argmx = from; mx = d;
        }

        for (auto to : E[from]){
            if (to == p) continue;
            _diameter(to, from, d+1, mx, argmx);
        }
    }

    //fromを根とする木の部分木のサイズを求める
    vector<S> subtree_size(S from) const{
        vector<S> subtree(N);
        _subtree_size(from, -1, subtree);
        return subtree;
    }

    S _subtree_size(S from, S p, vector<S> &subtree) const{
        S cnt = 1;

        for (auto to : E[from]){
            if (to == p) continue;
            cnt += _subtree_size(to, from, subtree);
        }

        return subtree[from] = cnt;
    }
};

const ll modc = 998244353;
class mint {
    ll x;
public:
    mint(ll x=0) : x((x%modc+modc)%modc) {}
    mint operator-() const {
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= modc) x -= modc;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += modc-a.x) >= modc) x -= modc;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= modc;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    mint inv() const {
        return pow(modc-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }
    bool operator == (const mint& a) const{
        return x == a.x;
    }
    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
    friend istream& operator>>(istream& ip, mint &m) {
        ll t;
        ip >> t;
        m = mint(t);
        return ip;
    }
};

int main(){

    ll N, C;
    mint ans=0;
    cin >> N;
    vector<ll> A(N-1), B(N-1);
    vector<vector<long long>> E(N);

    for (int i=0; i < N-1; i++){
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
        E[A[i]].push_back(B[i]);
        E[B[i]].push_back(A[i]);
    }

    Tree tree(E);
    vector<ll> subtree = tree.subtree_size(0);
    for (int i=0; i<N-1; i++){
        C = min(subtree[A[i]], subtree[B[i]]);
        ans += C * (N-C);
    }

    ans /= N;
    ans *= 2;
    ans /= (N-1);
    ans /= (N-1);

    cout << -ans+1 << endl;

    return 0;
}
0