566C - Logistical Questions - CodeForces Solution

// becoder Submission #undefined @ 1708084137086
#include<bits/stdc++.h>
#define rg register 
#define il inline
#define int long long
#define mp make_pair
#define PII pair<int, int>
using namespace std;

namespace FastIO {
    const int FAST_LEN = 1 << 20;

    static char ibuf[FAST_LEN], *iS, *iT;
    #define getchar() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, FAST_LEN, stdin), iS == iT ? EOF : *iS++ : *iS++)
    inline int read() { return 0; }
    template<typename T, typename... Arg>
    inline int read(T& val, Arg&... arg) {
        if (is_same<T, char>::value) {
            val = getchar();
            while (val == ' ' || val == '\n' || val == '\r') val = getchar();
            if (val == EOF) return 0;
        } else if (is_same<T, double>::value) {
            val = 0;
            register char x(getchar());
            register double frc = 1;
            register short g(1);
            register bool dec(0);
            while (x < '0' || x > '9') { if (x == EOF) return 0; g = (x == '-' ? -1 : g), x = getchar(); }
            while ((x >= '0' && x <= '9') || x == '.') {
                if (x == '.') dec = 1; else if (dec) frc *= 0.1, val = val + (x ^ 48) * frc; else val = val * 10 + (x ^ 48);
                x = getchar();
            }
            val *= g;
        } else {
            val = 0;
            register char x(getchar());
            register short g(1);
            while (x < '0' || x > '9') { if (x == EOF) return 0; g = (x == '-' ? -1 : g), x = getchar(); }
            while (x >= '0' && x <= '9') val = val * 10 + (x ^ 48), x = getchar();
            val *= g;
        }
        return read(arg...) + 1;
    }

    static char obuf[FAST_LEN], *iP = obuf;
    #define putchar(x) ((iP - obuf < FAST_LEN) ? (*iP++ = x) : (fwrite(obuf, iP - obuf, 1, stdout), iP = obuf, *iP++ = x))
    inline void write() { return; }
    inline void write(register int val) {
        if (val < 0) putchar('-'), write(-val);
        else { if (val > 9) write(val / 10); putchar(val % 10 ^ 48); }
    }
    inline void write(pair<int, int> val) {
        if (!val.second) write(val.first), putchar('.');
        else write(make_pair(val.first / 10, val.second - 1)), putchar(val.first % 10 ^ 48);
    }
    inline void write(pair<int, double> val) {
        if (val.second < 0) putchar('-'), val.second = -val.second;
        for (register int i = 1; i <= val.first; i++) val.second *= 10;
        write(make_pair((int)(val.second + 0.5), val.first));
    }
    inline void write(char val) { putchar(val); }
    template<typename T, typename... Arg>
    inline void write(T val, Arg... arg) {
        write(val);
        write(arg...);
    }
}
using namespace FastIO;

int n, m, k, ans1;
double ans2 = 1e20, w[500005], d[500005];
int rt, Mx[500005], siz[500005], all;
bool vis[500005];
vector<PII> G[500005];

il void GetRoot(int u, int fa) {
    siz[u] = 1 , Mx[u] = 0;
    for (auto to : G[u]) {
        int v = to.first;
        if (v == fa || vis[v]) continue;
        GetRoot(v, u);
        siz[u] += siz[v], Mx[u] = max(Mx[u] , siz[v]);
    }
    Mx[u] = max(Mx[u], all - siz[u]);
    if (Mx[u] < Mx[rt]) rt = u;
}

double sum1 , sum2;

il void Calc(int u, int fa, int rt, int dis) {
    sum1 += 1.0 * pow(dis , 1.5) * w[u], d[rt] += 1.5 * pow(dis , 0.5) * w[u];
    for (auto to : G[u]) {
        int v = to.first, w = to.second;
        if (v == fa) continue;
        Calc(v, u, rt, dis + w);
    }
}
il void Solve(int u) {
    vis[u] = 1, sum1 = sum2 = 0;
    for (auto to : G[u]) {
        int v = to.first, w = to.second;
        d[v] = 0, Calc(v, u, v, w);
        sum2 += d[v];
    }
    if (sum1 < ans2) ans2 = sum1, ans1 = u;
    for (auto to : G[u]) {
        int v = to.first, w = to.second;
        if (vis[v]) continue;
        if (sum2 - 2 * d[v] < 0) {
            all = siz[v], Mx[rt = 0] = 1e9;
            GetRoot(v , 0), Solve(rt);
            return;
        }
    }
}
signed main() {
    read(n);
    for (int i = 1; i <= n; i++) read(w[i]);
    for (int i = 1, u, v, w; i < n; i++) {
        read(u, v, w);
        G[u].push_back(mp(v , w)), G[v].push_back(mp(u , w));
    }
    Mx[rt = 0] = 1e9, all = n;
    GetRoot(1 , 0);
    Solve(rt);
    printf("%lld %.8lf", ans1, ans2);
    fwrite(obuf, iP - obuf, 1, stdout);
    return 0;
}