• https://oj.uz/problem/view/IZhO17_road

如果不考虑方案数的话是非常好写的，类似上一题，我们只需要维护向下的 top3 和向上的 top1 即可。
然后用均值不等式可以得到最优解一定是 a*(b+c) | a >= b >= c。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e5) + 9;

int dn[N][3], up[N];
VI adj[N]; int n;

void upd(int d[], int v) {
    if (v > d[0]) d[2] = d[1], d[1] = d[0], d[0] = v;
    else if (v > d[1]) d[2] = d[1], d[1] = v;
    else if (v > d[2]) d[2] = v;
}

void dfs1(int u = 1, int p = 0) {
    for (auto v: adj[u]) if (v != p) {
        dfs1(v, u);
        upd(dn[u], dn[v][0] + 1);
    }
}

void dfs2(int u = 1, int p = 0) {
    for (auto v: adj[u]) if (v != p) {
        checkMax(up[v], max(up[u], dn[u][0] != dn[v][0] + 1 ? dn[u][0] : dn[u][1]) + 1);
        dfs2(v, u);
    }
}

LL f(int x) {
    if (dn[x][1] == 0) return 0;
    if (up[x] > dn[x][0]) return (LL)up[x] * (dn[x][0] + dn[x][1]);
    if (up[x] > dn[x][2]) return (LL)dn[x][0] * (up[x] + dn[x][1]);
    if (dn[x][2] == 0) return 0;
    return (LL)dn[x][0] * (dn[x][1] + dn[x][2]);
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    DO(RD(n)-1) {
        int x, y; RD(x, y);
        adj[x].PB(y);
        adj[y].PB(x);
    }

    dfs1(); dfs2();

    LL z = 0; REP_1(i, n) checkMax(z, f(i));
    cout << z << endl;
}

考虑方案数的话，实现起来会麻烦很多。
主要上面的 a\b\c 里，a 是不参与计数的，只能各种讨论。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(5e5) + 9;

struct rec : public pair<LL, LL> {
    rec(LL a = 0, LL b = 0){
        fi = a, se = b;
    }
    rec& operator +=(const rec&r){
        if (fi == r.fi) se += r.se;
        else checkMax(*this, r);
        rTs;
    }
};

rec d[N], z = {0, 1};
VI adj[N]; int n;

void upd(rec d[], rec v) {
    if (v > d[0]) d[2] = d[1], d[1] = d[0], d[0] = v;
    else if (v > d[1]) d[2] = d[1], d[1] = v;
    else if (v > d[2]) d[2] = v;
}

void dfs1(int u = 1, int p = 0) {
    d[u] = {0, 1};
    for (auto v: adj[u]) if (v != p) {
        dfs1(v, u);
        d[u] += d[v];
    }
    d[u].fi += 1;
}

void dfs2(int u = 1, int p = 0, rec up = {0, 1}) {

    rec f[3] = {up};
    for (auto v: adj[u]) if (v != p) upd(f, d[v]);

    if (f[2].fi) {
        LL best = f[0].fi * (f[1].fi + f[2].fi);
        if (best >= z.fi) {
            LL ways, ways2 = up.fi == f[2].fi ? up.se : 0;
            for (auto v: adj[u]) if (v != p) if (d[v].fi == f[2].fi) ways2 += d[v].se;

            if (f[1].fi == f[2].fi) {
                ways = sqr(ways2);
                if (up.fi == f[2].fi) ways -= sqr(up.se);
                for (auto v: adj[u]) if (v != p) if (d[v].fi == f[2].fi) ways -= sqr(d[v].se);
                ways /= 2;
            } else {
                ways = ((f[0].fi == f[1].fi ? f[0].se : 0) + f[1].se) * ways2;
            }
            z += rec(best, ways);
        }
    }

    LL ways0 = 0, ways1 = 0;
    if (up.fi == f[0].fi) ways0 += up.se;
    else if (up.fi == f[1].fi) ways1 += up.se;
    for (auto v: adj[u]) if (v != p) {
        if (d[v].fi == f[0].fi) ways0 += d[v].se;
        else if (d[v].fi == f[1].fi) ways1 += d[v].se;
    }

    for (auto v: adj[u]) if (v != p) {
        LL a = f[0].fi+1, b = ways0;
        if (d[v].fi == f[0].fi) {
            if (d[v].se == ways0) a = f[1].fi+1, b = ways1;
            else b = ways0 - d[v].se;
        }
        dfs2(v, u, {a, b});
    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    DO(RD(n)-1) {
        int x, y; RD(x, y);
        adj[x].PB(y);
        adj[y].PB(x);
    }

    dfs1(); dfs2();
    cout << z.fi << " " << z.se << endl;
}

Posted by xiaodao
Category: 日常