• https://www.spoj.com/problems/TWOPATHS/
• https://codeforces.com/problemset/problem/14/D

题意：求两条不相交路径的积的最大值。

分析：dfs 序维护直径 有一个非常棒的性质。。。就是可以求子树内的直径和子树外的直径。。所以我们只要再 dfs 一次，然后每次 query 出来两个直径乘一下。。可惜 O(nlogn) 也许过不了大数据。。。

#include <lastweapon/io>
using namespace lastweapon;

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

int L[N], R[N], dep[N], id[N], nn;
VI adj[N]; int n;

struct rec{
    int d, dd, ld, rd, D;
    void init(LL _d, LL _dd) {
        d = _d; dd = 2*_dd;
        D = ld = -INF; rd = _d - dd;
    }
} T[N*4];

// max d[l] + d[r] - dd[m]
// l < m <= r
// d 深度
// dd 父亲的深度

#define lx (x<<1)
#define rx (lx|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx,l,ml
#define rc rx,mr,r
void upd(int x) {
    T[x].d = max(T[lx].d, T[rx].d);
    T[x].dd = min(T[lx].dd, T[rx].dd);
    T[x].ld = max(T[lx].ld, T[rx].ld, T[lx].d - T[rx].dd);
    T[x].rd = max(T[lx].rd, T[rx].rd, T[rx].d - T[lx].dd);
    T[x].D = max(T[lx].D, T[rx].D, T[lx].ld + T[rx].d, T[lx].d + T[rx].rd);
}

rec upd(rec l, rec r) {
    rec x;
    x.d = max(l.d, r.d);
    x.dd = min(l.dd, r.dd);
    x.ld = max(l.ld, r.ld, l.d - r.dd);
    x.rd = max(l.rd, r.rd, r.d - l.dd);
    x.D = max(l.D, r.D, l.ld + r.d, l.d + r.rd);
    return x;
}

void Build(int x, int l, int r) {
    if (l == r) {
        T[x].init(dep[id[l]], dep[id[l]]-1);
    } else {
        Build(lc);
        Build(rc);
        upd(x);
    }
}
void dfs(int u = 1, int p = 0) {
    id[L[u] = ++nn] = u;
    for (auto v: adj[u]) if (v != p) {
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
    R[u] = nn;
}

rec Query(int x, int l, int r, int a, int b) {
    /*if (b < l || r < a) {
        rec x; x.init(-INF,INF);
        return x;
    }*/
    if (a <= l && r <= b) {
        return T[x];
    } else {

        if (b < mr) return Query(lc, a, b);
        if (ml < a) return Query(rc, a, b);
        return upd(Query(lc, a, b), Query(rc, a, b));
    }
}

LL z = 0;
void gao(int u = 1, int p = 0) {
    for (auto v: adj[u]) if (v != p) {
        LL D = Query(1,1,n,L[v],R[v]).D;
        checkMax(z, D * upd(Query(1,1,n,1,L[v]-1), Query(1,1,n,R[v]+1,n)).D);

        /*cout << L[v] << " " << R[v] << " " << v << " " << Query(1,1,n,L[v],R[v]).D << " " <<
         upd(Query(1,1,n,1,L[v]-1), Query(1,1,n,R[v]+1,n)).D
         << " " << z << endl;*/
        gao(v, u);
    }
}

int main() {

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

    dep[0] = INF;

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

    if (n > 3) {
        dfs(); Build(1, 1, n); gao();
    }
    cout << z << endl;
}

没办法，只能换根 dp 了。

#include <lastweapon/io>
using namespace lastweapon;

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

int dn[N], up[N]; // 子树内直径，子树外直径
int d[N][3], e[N]; // 子数内 top3 最长距离，子树外最长距离
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(d[u], d[v][0] + 1);
        checkMax(dn[u], dn[v]);
    }
    checkMax(dn[u], d[u][0] + d[u][1]);
}

void dfs2(int u = 1, int p = 0) {
    for (auto v: adj[u]) if (v != p) {
        checkMax(up[v], up[u]);
        checkMax(e[v], e[u] + 1);
        int t = d[v][0] + 1;
        if (d[u][0] == t) {
            checkMax(up[v], d[u][1] + d[u][2]);
            checkMax(up[v], d[u][1] + e[u]);
            checkMax(e[v], d[u][1] + 1);
        }
        else {
            if (d[u][1] == t) checkMax(up[v], d[u][0] + d[u][2]);
            else checkMax(up[v], d[u][0] + d[u][1]);
            checkMax(up[v], d[u][0] + e[u]);
            checkMax(e[v], d[u][0] + 1);
        }
        dfs2(v, u);
    }
}

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; FOR_1(i, 2, n) checkMax(z, (LL)dn[i] * up[i]);
    cout << z << endl;
}

Posted by xiaodao
Category: 日常