結果

問題 No.1333 Squared Sum
ユーザー Kite_kuma
提出日時 2021-01-08 23:59:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 442 ms / 2,000 ms
コード長 22,281 bytes
コンパイル時間 2,148 ms
コンパイル使用メモリ 198,748 KB
実行使用メモリ 135,936 KB
最終ジャッジ日時 2024-11-16 18:59:22
合計ジャッジ時間 12,183 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/*  author:  Kite_kuma
    created: 2021.01.08 22:06:52 */
// #ifdef LOCAL
// #define _GLIBCXX_DEBUG
// #endif
#include <bits/stdc++.h>
using namespace std;
#pragma region aliases
#define rep(i, n) for(long long i = 0; i < (n); i++)
#define rrep(i, n) for(long long i = (n)-1; i > -1; i--)
#define Rep(i, m, n) for(long long i = (m); i < (n); i++)
#define rRep(i, m, n) for(long long i = (n)-1; i >= (m); i--)
#define REP(i, m, n, p) for(long long i = m; i < n; i += p)
#define foa(s, v) for(auto &s : v)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define bcnt(n) __builtin_popcountll(n)
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vb = vector<bool>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
template <class T = ll>
using V = vector<T>;
template <class T = ll>
using VV = V<V<T>>;
template <class T = ll>
using VVV = V<V<V<T>>>;
template <class T = ll>
using pqup = priority_queue<T, vector<T>, greater<T>>;
template <class T = ll>
using pqdn = priority_queue<T>;
#pragma endregion
#pragma region constants
long long const dekai = 1e18;
const long double pi = acos(-1);
const char dl = '\n';
const char sp = ' ';
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int mod = 1000000007;
// const int mod = 998244353;
#pragma endregion
#pragma region basic_procedure
template <class T>
inline bool isin(T x, T lef, T rig) {
    return ((lef <= x) && (x < rig));
}
template <class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
void Yes(bool f = 1) { cout << (f ? "Yes" : "No") << '\n'; }
void No() { cout << "No\n"; }
void YES(bool f = 1) { cout << (f ? "YES" : "NO") << '\n'; }
void NO() { cout << "NO\n"; }
template <class T>
void drop(T answer) {
    cout << answer << '\n';
    exit(0);
}
void err(bool flag) {
    if(!flag) return;
    cout << -1 << '\n';
    exit(0);
}
template <class T>
void vout(vector<T> const &v, bool tate = 0) {
    if(tate) {
        for(auto const &a : v) {
            cout << a << '\n';
        }
        return;
    }
    for(auto it = v.begin(); it != v.end(); it++) {
        cout << (*it);
        if(it != v.end() - 1) {
            cout << ' ';
        }
    }
    cout << '\n';
    return;
}
inline void print() { cout << '\n'; }
template <class T>
inline void print(T x) {
    cout << x << '\n';
    return;
}
template <typename Head, typename... Tail>
void print(Head H, Tail... T) {
    cout << H << " ";
    print(T...);
}
template <class T>
void add(vector<T> &v, T val) {
    for(auto &a : v) a += val;
    return;
}
template <class T>
T dup(T a, T b) {
    assert(b != 0);
    T x = abs(a);
    T y = abs(b);
    T z = (x + y - 1) / y;
    if((a < 0 && b > 0) || (a > 0 && b < 0))
        return -z;
    else if(a == 0)
        return 0;
    else
        return z;
}
template <class T>
T greatest_lower_multiple(T x, T d) {
    if(d == 0) return 0;
    if(d < 0) d *= -1;
    T y = x % d;
    if(y < 0) y += d;
    return x - y;
}
template <class T>
T least_upper_multiple(T x, T d) {
    return -greatest_lower_multiple(-x, d);
}
long long POW(long long a, long long n) {
    long long res = 1;
    while(n > 0) {
        if(n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}
long long modpow(long long a, long long n, long long mod) {  // a^n mod
    assert(n >= 0);
    if(mod == 1) return 0LL;
    long long res = 1;
    while(n > 0) {
        if(n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
// a * x % mod == __gcd(a,mod)なるxを返す
// a が modの倍数でないことが条件
long long modinv(long long a, long long mod) {
    long long b = mod, u = 1, v = 0;
    while(b) {
        long long t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= mod;
    if(u < 0) u += mod;
    return u;
}
vvll comb(100, vll(100, -1));
long long com(long long n, long long k) {  //普通の二項計数
    assert(n < 100 && k < 100);
    if(n < k || k < 0 || n < 0) return 0;
    if(comb[n][k] != -1) return comb[n][k];
    ll res;
    if(n - k < k)
        res = com(n, n - k);
    else if(k == 0)
        res = 1;
    else
        res = com(n - 1, k - 1) + com(n - 1, k);
    comb[n][k] = res;
    return res;
}
const int MAX = 5100000;  // about 300ms, when MAX = 3*10^7 : 1900ms
long long fac[MAX], finv[MAX], inv[MAX];
void cominit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}
long long commod(long long n, long long k) {
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
long long pmod(long long n, long long k) {
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * finv[n - k] % mod;
}
// n個の区別しないボールを区別するk個の箱に入れる方法の総数
long long hmod(long long n, long long k) {  // 重複組み合わせ
    return commod(n + k - 1, n);
}
#pragma endregion
#pragma region input
#define VEC(type, name, size) \
    vector<type> name(size);  \
    INPUT(name)
#define VVEC(type, name, h, w)                     \
    vector<vector<type>> name(h, vector<type>(w)); \
    INPUT(name)
#define INT(...)     \
    int __VA_ARGS__; \
    INPUT(__VA_ARGS__)
#define LL(...)            \
    long long __VA_ARGS__; \
    INPUT(__VA_ARGS__)
#define STR(...)        \
    string __VA_ARGS__; \
    INPUT(__VA_ARGS__)
#define CHAR(...)     \
    char __VA_ARGS__; \
    INPUT(__VA_ARGS__)
#define DOUBLE(...)     \
    double __VA_ARGS__; \
    INPUT(__VA_ARGS__)
#define LD(...)              \
    long double __VA_ARGS__; \
    INPUT(__VA_ARGS__)
template <class T>
void scan(T &a) {
    cin >> a;
}
template <class T>
void scan(vector<T> &a) {
    for(auto &i : a) scan(i);
}
template <class T, class L>
void scan(pair<T, L> &p) {
    scan(p.first);
    scan(p.second);
}
void INPUT() {}
template <class Head, class... Tail>
void INPUT(Head &head, Tail &... tail) {
    scan(head);
    INPUT(tail...);
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}
#pragma endregion
#pragma region debug
#pragma region output
template <typename T1, typename T2>
std::ostream &std::operator<<(std::ostream &os, const std::pair<T1, T2> &p) {
    os << p.first << " " << p.second;
    return os;
}
template <class T>
std::ostream &std::operator<<(std::ostream &os, const std::vector<T> &v) {
    for(int i = 0; i < (int)v.size(); i++) {
        if(i) os << " ";
        os << v[i];
    }
    return os;
}
#pragma endregion
#pragma region view
template <typename T>
void view(const T e) {
    std::cerr << e;
}
template <typename T, typename U>
void view(const std::pair<T, U> &p) {
    std::cerr << "(";
    view(p.first);
    std::cerr << ", ";
    view(p.second);
    std::cerr << ")";
}
template <typename T>
void view(const std::set<T> &s) {
    if(s.empty()) {
        std::cerr << "{ }";
        return;
    }
    std::cerr << "{ ";
    for(auto &t : s) {
        view(t);
        std::cerr << ", ";
    }
    std::cerr << "\b\b }";
}
template <typename T>
void view(const std::unordered_set<T> &s) {
    if(s.empty()) {
        std::cerr << "{ }";
        return;
    }
    std::cerr << "{ ";
    for(auto &t : s) {
        view(t);
        std::cerr << ", ";
    }
    std::cerr << "\b\b }";
}
template <typename T>
void view(const std::vector<T> &v) {
    if(v.empty()) {
        std::cerr << "{ }";
        return;
    }
    std::cerr << "{ ";
    for(const auto &e : v) {
        view(e);
        std::cerr << ", ";
    }
    std::cerr << "\b\b }";
}
template <typename T>
void view(const std::vector<std::vector<T>> &vv) {
    std::cerr << "{\n";
    for(const auto &v : vv) {
        std::cerr << "\t";
        view(v);
        std::cerr << '\n';
    }
    std::cerr << "}";
}
template <typename T, typename U>
void view(const std::vector<std::pair<T, U>> &v) {
    std::cerr << "{\n";
    for(const auto &c : v) {
        std::cerr << "\t(";
        view(c.first);
        std::cerr << ", ";
        view(c.second);
        std::cerr << ")\n";
    }
    std::cerr << "}";
}
template <typename T, typename U>
void view(const std::map<T, U> &m) {
    std::cerr << "{\n";
    for(const auto &t : m) {
        std::cerr << "\t[";
        view(t.first);
        std::cerr << "] : ";
        view(t.second);
        std::cerr << '\n';
    }
    std::cerr << "}";
}
template <typename T, typename U>
void view(const std::unordered_map<T, U> &m) {
    std::cerr << "{\n";
    for(const auto &t : m) {
        std::cerr << "\t[";
        view(t.first);
        std::cerr << "] : ";
        view(t.second);
        std::cerr << '\n';
    }
    std::cerr << "}";
}
#pragma endregion
// when debugging : g++ foo.cpp -DLOCAL
#ifdef LOCAL
void debug_out() {}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    view(H);
    std::cerr << ", ";
    debug_out(T...);
}
#define debug(...)                                                \
    do {                                                          \
        std::cerr << __LINE__ << " [" << #__VA_ARGS__ << "] : ["; \
        debug_out(__VA_ARGS__);                                   \
        std::cerr << "\b\b]\n";                                   \
    } while(0)
#define dump(x)                                      \
    do {                                             \
        std::cerr << __LINE__ << " " << #x << " : "; \
        view(x);                                     \
        std::cerr << '\n';                           \
    } while(0)
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
#pragma endregion
#pragma region modint
template <int mod>
struct ModInt {
    int x;
    ModInt() : x(0) {}
    ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator*=(const ModInt &p) {
        x = (int)(1LL * x * p.x % mod);
        return *this;
    }
    ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }
    ModInt operator-() const { return ModInt(-x); }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    bool operator==(const ModInt &p) const { return x == p.x; }
    bool operator!=(const ModInt &p) const { return x != p.x; }
    ModInt inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }
    ModInt pow(long long n) const {
        ModInt ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
    friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; }
    friend istream &operator>>(istream &is, ModInt &a) {
        long long t;
        is >> t;
        a = ModInt<mod>(t);
        return (is);
    }
    static int get_mod() { return mod; }
};
using mint = ModInt<mod>;
#pragma endregion
#pragma region graph_structure
template <class T = long long>
struct edge {
    T len;
    int from;
    int to;
    bool operator<(const edge a) const {
        if(len != a.len) return len < a.len;
        if(from != a.from) return from < a.from;
        return to < a.to;
    }
    bool operator>(const edge a) const {
        if(len != a.len) return len > a.len;
        if(from != a.from) return from > a.from;
        return to > a.to;
    }
};
template <class T = long long>
struct graph {  // 0-indexed
    T const INF = numeric_limits<T>::max() / 3;
    vector<vector<edge<T>>> edges;
    int ver;
    // constructor
    graph() = default;
    graph(int vertex) : ver(vertex), edges(vertex) {}
    //辺の追加 (0-indexed)
    void update(int from, int to, T len = 1, bool direction = 1) {  // checked
        edge<T> e;
        e.len = len;
        e.from = from;
        e.to = to;
        edges[from].push_back(e);
        if(!direction) {
            swap(e.to, e.from);
            edges[to].push_back(e);
        }
    }
    //入力受取 (1-indexed)
    void input(int edge_num, bool direction = false, bool weight = false, int index = 1) {  // checked
        for(int i = 0; i < edge_num; i++) {
            int a;
            int b;
            cin >> a >> b;
            a -= index;
            b -= index;
            T c;
            if(weight)
                cin >> c;
            else
                c = 1;
            update(a, b, c, direction);
        }
    }
    // 辺の長さを全て1とみたときの単一始点最短経路 (無理なときはINF)
    vector<T> bfs(int start) {  // checked
        // https://atcoder.jp/contests/abc007/submissions/me
        vector<T> ret(ver, INF);
        queue<int> q;
        q.push(start);
        ret[start] = 0;
        while(!q.empty()) {
            int now = q.front();
            q.pop();
            for(auto &e : edges[now]) {
                if(ret[e.to] != INF) continue;
                q.push(e.to);
                ret[e.to] = ret[now] + 1;
            }
        }
        return ret;
    }
    //長さが負のpathがないときの単一始点最短経路<vll> O((ver)log(ver)+(edge))
    vector<T> dijkstra(int start) {  // checked
        // https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/GRL_1_A/judge/4817136/C++14
        vector<T> ret(ver, (T)INF);                                                   //{dist,place}
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> p;  //{dist,place}
        p.push({0, start});
        ret[start] = 0;
        while(!p.empty()) {
            T dist = p.top().first;
            int place = p.top().second;
            p.pop();
            if(ret[place] < dist) continue;
            for(auto &next : edges[place]) {
                int nextplace = next.to;
                T dis = next.len;
                if(ret[nextplace] > dist + dis) {
                    ret[nextplace] = dist + dis;
                    p.push({ret[nextplace], nextplace});
                }
            }
        }
        return ret;
    }
    //単一始点最短経路 O((ver)*(edge))
    //辿り着けないとき ret[i] = INF;
    //ある頂点までのコストが無限に小さくなり得るとき→ ret[i] = -INF;
    vector<T> BellmanFord(int start) {  // checked
        // https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/GRL_1_B/judge/4817139/C++14
        vector<T> ret(ver, INF);
        ret[start] = 0;
        for(int loop = 0; loop < ver - 1; loop++) {
            for(int v = 0; v < ver; v++) {
                if(ret[v] == INF) continue;
                for(auto &e : edges[v]) {
                    ret[e.to] = min(ret[e.to], ret[v] + e.len);
                }
            }
        }
        //無限降下点の検索
        queue<int> q;
        vector<bool> chk(ver, 0);
        for(int v = 0; v < ver; v++) {
            if(ret[v] == INF) continue;
            for(auto &e : edges[v]) {
                if(ret[e.to] > ret[v] + e.len) {
                    ret[e.to] = ret[v] + e.len;
                    if(!chk[e.to]) {
                        q.push(e.to);
                        chk[e.to] = 1;
                    }
                }
            }
        }
        while(!q.empty()) {
            int now = q.front();
            q.pop();
            for(auto &e : edges[now]) {
                if(!chk[e.to]) {
                    chk[e.to] = 1;
                    q.push(e.to);
                }
            }
        }
        for(int i = 0; i < ver; i++)
            if(chk[i]) ret[i] = -INF;
        return ret;
    }
    //閉路に含まれない頂点列挙
    //要素数がver未満なら閉路が存在、そうでなければ閉路は存在しない
    vector<int> topo_sort() {  // checked
        // https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/GRL_4_B/judge/4817106/C++14
        // https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/GRL_4_A/judge/4817110/C++14
        vector<int> num_input(ver);
        // 入次数
        for(int i = 0; i < ver; i++) {
            for(auto e : edges[i]) {
                num_input[e.to]++;
            }
        }
        // 入次数が0のノードをqueueで管理する
        queue<int> que;
        for(int i = 0; i < ver; i++) {
            if(num_input[i] == 0) {
                que.push(i);
            }
        }
        vector<int> ans;
        while(!que.empty()) {
            auto node = que.front();
            que.pop();
            ans.push_back(node);
            // 頂点の削除
            for(auto e : edges[node]) {
                num_input[e.to]--;
                // 行き先の入次数が0になったらqueueに追加
                if(num_input[e.to] == 0) {
                    que.push(e.to);
                }
            }
        }
        return ans;
    }
    //{{端点、端点},直径の大きさ}
    pair<pair<int, int>, T> DiameterOfTree(bool weigh = true) {  // chkecked
        // https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/GRL_5_A/judge/4817099/C++14
        vector<T> vec;
        vec = weigh ? dijkstra(0) : bfs(0);
        int v1 = -1;
        T dia = -1;
        for(int i = 0; i < ver; i++)
            if((dia < vec[i])) {
                dia = vec[i];
                v1 = i;
            }
        vec = weigh ? dijkstra(v1) : bfs(v1);
        dia = -1;
        int v2 = -1;
        for(int i = 0; i < ver; i++)
            if((dia < vec[i])) {
                v2 = i;
                dia = vec[i];
            }
        pair<pair<int, int>, T> ans = {{v1, v2}, dia};
        return ans;
    }
    //無向木構造を根から葉に伸びる有向木構造に書き換える
    graph<T> RootToLeaf(int root) {  // 0-indexed
        graph<T> ret(ver);
        vector<bool> chk(ver, 0);
        chk[root] = 1;
        function<void(int)> dfs = [&](int now) {
            for(auto &e : edges[now]) {
                if(chk[e.to] == 1) continue;
                chk[e.to] = 1;
                ret.update(now, e.to, e.len);
                dfs(e.to);
            }
        };
        dfs(root);
        return ret;
    }
    //無向木構造を葉から根に伸びる有向木構造に書き換える
    graph<T> LeafToRoot(int root) {  // 0-indexed
        graph<T> ret(ver);
        vector<bool> chk(ver, 0);
        chk[root] = 1;
        function<void(int)> dfs = [&](int now) {
            for(auto &e : edges[now]) {
                if(chk[e.to] == 1) continue;
                chk[e.to] = 1;
                ret.update(e.to, now, e.len);
                dfs(e.to);
            }
        };
        dfs(root);
        ret.update(root, root, 0);
        return ret;
    }
    // LeafToRootのvector版.par[i]=iの親の頂点
    vector<int> par(int root) {  // 0-indexed
        vector<int> ret(ver, -1);
        ret[root] = root;  // rootの親はroot
        function<void(int)> dfs = [&](int now) {
            for(auto &e : edges[now]) {
                if(ret[e.to] != -1) continue;
                ret[e.to] = now;
                dfs(e.to);
            }
        };
        dfs(root);
        return ret;
    }
    vector<edge<T>> ParentAndDistance(int root) {  // 0-indexed
        vector<edge<T>> ret(ver);
        for(int i = 0; i < ver; i++) ret[i].to = -1;
        ret[root].to = root;  // rootの親はroot
        ret[root].len = 0;    // rootの親との距離は0
        function<void(int)> dfs = [&](int now) {
            for(auto &e : edges[now]) {
                if(ret[e.to].to != -1) continue;
                ret[e.to].to = now;
                ret[e.to].len = e.len;
                dfs(e.to);
            }
        };
        dfs(root);
        return ret;
    }
    //隣接sheet.主にwarshall用
    vector<vector<T>> GraphArray(void) {  // chkecked
        // https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/GRL_1_C/judge/4817090/C++14
        vector<vector<T>> ret(ver, vector<T>(ver, INF));
        for(int from = 0; from < ver; from++) {
            for(auto &e : edges[from]) {
                ret[from][e.to] = e.len;
            }
            ret[from][from] = 0;
        }
        return ret;
    }
    graph<T> Prim(bool direction = 0, int start = 0) {  // checked
        // https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/GRL_2_A/judge/4817129/C++14
        graph<T> ret(ver);
        priority_queue<edge<T>, vector<edge<T>>, greater<edge<T>>> p;
        for(auto &e : edges[start]) {
            p.push(e);
        }
        vector<bool> chk(ver, 0);
        chk[start] = 1;
        while(!p.empty()) {
            auto ed = p.top();
            p.pop();
            if(chk[ed.to]) continue;
            chk[ed.to] = 1;
            ret.update(ed.from, ed.to, ed.len, direction);
            for(auto &e : edges[ed.to]) {
                p.push(e);
            }
        }
        return ret;
    }
    //各頂点を根としたときの木の高さ
    vector<T> height(int start = 0) {  // checked
        // https://onlinejudge.u-aizu.ac.jp/status/users/Kite_kuma/submissions/1/GRL_5_B/judge/4817082/C++14
        vector<T> fir(ver, -1), sec(ver, -1);
        function<T(int, int)> dfs = [&](int now, int par) {
            T f = 0, s = 0;  // startを根としたときのnowからの深さ1番目、2番目
            for(auto &e : edges[now]) {
                if(e.to == par) continue;
                s = max(s, dfs(e.to, now) + e.len);
                if(f < s) swap(f, s);
            }
            sec[now] = s;
            return fir[now] = f;
        };
        dfs(start, -1);
        function<void(int, int, T, T, T)> sol = [&](int now, int par, T parf, T pars, T parlen) {
            if(fir[now] + parlen == parf) parf = pars;
            sec[now] = max(sec[now], parf + parlen);
            if(fir[now] < sec[now]) swap(fir[now], sec[now]);
            for(auto &e : edges[now]) {
                if(e.to == par) continue;
                sol(e.to, now, fir[now], sec[now], e.len);
            }
            return;
        };
        sol(start, -1, -1, -1, -1);
        return fir;
    }
    //全方位木DP
    //マージ関数、上に送るための関数、単位元、はじめの根
    // 関数はstd::functionで渡す
    template <class U>
    vector<U> ReRootingDP(U &unit, function<U(U, U)> &merge, function<U(int, U, T)> &send, int root = 0) {
        auto tr = RootToLeaf(root);
        vector<vector<U>> v(ver);
        vector<U> ret(ver);  //求める答
        function<U(int)> treeDP = [&](int now) {
            U res = unit;
            vector<U> vec;
            for(auto &e : tr.edges[now]) {
                U u = send(e.to, treeDP(e.to), e.len);
                v[now].push_back(u);
                res = merge(res, u);
            }
            return res;
        };
        treeDP(root);
        function<void(int, U, int, T)> rerooting = [&](int now, U ans_par, int par, T len) {
            if(now != root) ans_par = send(par, ans_par, len);
            int sz = v[now].size();
            vector<U> data_front(sz + 1), data_back(sz + 1);
            data_front[0] = data_back[sz] = unit;
            for(int i = 0; i < sz; i++) {
                data_front[i + 1] = merge(data_front[i], v[now][i]);
                data_back[sz - i - 1] = merge(v[now][sz - i - 1], data_back[sz - i]);
            }
            for(int i = 0; i < sz; i++) {
                auto nxtans = merge(ans_par, merge(data_front[i], data_back[i + 1]));
                rerooting(tr.edges[now][i].to, nxtans, now, tr.edges[now][i].len);
            }
            ret[now] = merge(ans_par, data_front[sz]);
            return;
        };
        rerooting(root, unit, root, 0);
        return ret;
    }
    // HL分解
};
#pragma endregion
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    srand((unsigned)time(NULL));
    INT(n);
    mint ans = 0;
    using data = tuple<int, mint, mint>;  // size, dist_sum, square_sum
    graph<> gra(n);
    gra.input(n - 1, 0, 1);
    function<data(data, data)> merge = [](data a, data b) {
        int size_a, size_b;
        mint dist_a, dist_b, sq_a, sq_b;
        tie(size_a, dist_a, sq_a) = a;
        tie(size_b, dist_b, sq_b) = b;
        int fir = size_a + size_b;
        mint sec = dist_a + dist_b;
        mint thir = sq_a + sq_b;
        return (data){fir, sec, thir};
    };
    function<data(int, data, ll)> send = [&](int id, data predata, ll len) {
        int size;
        mint dist, sq;
        tie(size, dist, sq) = predata;
        size += 1;
        sq += (mint)size * (mint)len * (mint)len + (mint)2 * (mint)len * dist;
        dist += (mint)len * size;
        return (data){size, dist, sq};
    };
    data unit = data(0, 0, 0);
    vector<data> res = gra.ReRootingDP(unit, merge, send);
    foa(t, res) {
        ans += get<2>(t);
        debug(get<0>(t), get<1>(t), get<2>(t));
    }
    drop(ans / 2);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0