Submission #968410

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }

template <class E>
using Graph = vector<vector<E>>;

struct Centroid {
    int r;
    Graph<int> cg;
    vector<int> par;
    vector<bool> used;

    using P = pair<int, int>;
    vector<P> info; //(child max, child)
    template<class E>
    int dfs(const Graph<E> &g, int p, int b) {
        int sz = 1;
        info[p] = P(0, -1);
        for (E e: g[p]) {
            int d = e.to;
            if (d == b || used[d]) continue;
            int csz = dfs(g, d, p);
            sz += csz;
            info[p] = max(info[p], P(csz, d));
        }
        return sz;
    }
    template<class E>
    int init(const Graph<E> &g, int p, int b) {
        int sz = dfs(g, p, -1);
        while (info[p].first > sz/2) p = info[p].second;
        par[p] = b;
        used[p] = true;
        for (E e: g[p]) {
            int d = e.to;
            if (used[d]) continue;
            cg[p].push_back(init(g, d, p));
        }
        return p;
    }
    Centroid() {}
    template<class E>
    Centroid(const Graph<E> &g) {
        int n = (int)g.size();
        cg = Graph<int>(n);
        par = vector<int>(n);
        used = vector<bool>(n, false);
        info = vector<P>(n);
        r = init(g, 0, -1);
    }
};

template<class C>
struct CentDist {
    using P = pair<int, C>; //root, dist
    vector<vector<P>> plist;
    vector<bool> used;

    template<class E>
    void dfs(const Graph<E> &g, int p, int b, int r, C dp = 0) {
        plist[p].push_back(P(r, dp));
        for (const E &e: g[p]) {
            int d = e.to;
            if (used[d] || d == b) continue;
            dfs(g, d, p, r, dp+e.dist);
        }
    }

    template<class E>
    void init(const Graph<E> &g, const Centroid &cen, int p) {
        dfs(g, p, -1, p);
        //nex
        used[p] = true;
        for (int d: cen.cg[p]) {
            init(g, cen, d);
        }
    }

    CentDist() {}
    template<class E>
    CentDist(const Graph<E> &g, const Centroid &cen) {
        int n = int(g.size());
        plist = vector<vector<P>>(n);
        used = vector<bool>(n);
        init(g, cen, cen.r);
    }
};


using P = pair<ll, ll>;

struct Node {
    using NP = Node*;

    ll fe;
    P sm;

    /*
     init_node, update, push
    */
    void init_node(ll fe) {
        this->fe = fe;
        sm = P(0, 0);
    }
    void update() {
        sm = P(l->sm.first+r->sm.first, l->sm.second+r->sm.second);
    }
    void push() {
    }
    void lzdata(int x) {
        sm.first += x;
        sm.second += fe*x;
    }

    void add(int k, ll x) {
        if (sz == 1) {
            lzdata(x);
            return;
        }
        push();
        if (k < sz/2) {
            l->add(k, x);
        } else {
            r->add(k-sz/2, x);
        }
        update();
    }
    P get(int a, int b) {
        if (b <= 0 or sz <= a) return P(0, 0);
        if (a <= 0 and sz <= b) {
            return sm;
        }
        push();
        P lp = l->get(a, b);
        P rp = r->get(a-sz/2, b-sz/2);
        return P(lp.first+rp.first, lp.second+rp.second);
    }

    NP l, r;
    int sz;
    Node(int sz, int offset = 0) : sz(sz) {
        init_node(offset);
        if (sz == 1) return;
        l = new Node(sz/2, offset);
        r = new Node(sz - sz/2, offset + sz/2);
        update();
    }
};


const int MN = 100100;
const int MX = 100100;

struct Edge {
    int to;
    ll dist;
};

ll x;

Graph<Edge> g;
Centroid cen;
Node* tr = new Node(MX);
vector<bool> used(MN, false);

ll sm, co;

void cdfs(int p, int b, ll dps, int k) {
    if (used[p]) return;
//    printf("cdfs %d %d %lld %d %lld\n", p, b, dps, k, x);
    if (x < dps) return;
    tr->add(dps, k);
    for (Edge e: g[p]) {
        int d = e.to;
        if (d == b) continue;
        cdfs(d, p, dps+e.dist, k);
    }
}


void adddfs(int p, int b, ll dps) {
    if (used[p]) return;
    if (x < dps) return;
    P ps = tr->get(0, x-dps+1);
//    printf("%lld %lld\n", ps.first, ps.second);

    co += ps.first;
    sm += ps.second + ps.first * dps;

    for (Edge e: g[p]) {
        int d = e.to;
        if (d == b) continue;
        adddfs(d, p, dps+e.dist);
    }
}

void dfs(int p) {
//    printf("dfs %d\n", p);
    tr->add(0, 1);
    for (Edge e: g[p]) {
        adddfs(e.to, p, e.dist);
        cdfs(e.to, p, e.dist, 1);
    }
    tr->add(0, -1);
    for (Edge e: g[p]) {
        cdfs(e.to, p, e.dist, -1);
    }
    used[p] = true;
    for (int d: cen.cg[p]) {
        dfs(d);
    }
}

multiset<ll> ms[MN];
int main() {
    ios::sync_with_stdio(0);
    int n;
    cin >> n >> x;
    g = Graph<Edge>(n);
    for (int i = 0; i < n-1; i++) {
        int a, b; ll c;
        cin >> a >> b >> c; a--; b--;
        g[a].push_back(Edge{b, c});
        g[b].push_back(Edge{a, c});
        ms[a].insert(c);
        ms[b].insert(c);
    }
    sm = 0;
    cen = Centroid(g);
    dfs(cen.r);

    for (int i = 0; i < n; i++) {
        for (auto e: g[i]) {
            int j = e.to;
            if (j < i) continue;
            if (x < e.dist) {
                co++;
                ll ans = TEN(12);
                if (g[i].size() + g[j].size() < n) {
                    ans = min(ans, 2*x);
                }
                ms[i].erase(ms[i].find(e.dist));
                ms[j].erase(ms[j].find(e.dist));
                ll f = TEN(12);
                if (ms[i].size()) {
                    f = min(f, *ms[i].begin());
                }
                if (ms[j].size()) {
                    f = min(f, *ms[j].begin());
                }
                ms[i].insert(e.dist);
                ms[j].insert(e.dist);
                ans = min(ans, x+f);

                sm += min(e.dist, ans);
            }
        }
    }
//    printf("%lld\n", co);
    sm += (ll(n)*(n-1)/2 - co) * x;
    printf("%lld\n", sm);
    return 0;
}

Submission Info

Judge Result