Problem F. Rook Score

我们记录每一行和每一列的和 R[], C[]，那么答案是某个 R[] + C[] – X[][]
注意这里 X[][] 可能在输入里，也可能不在，前者只有 O(n) 种，
后者对每一个 R，我们只要找其中最大的 C，所以其实也只有 O(n) 种。

排序后二重循环加个剪枝即可。

#include <lastweapon/io>
using namespace lastweapon;
const int N = int(2e5) + 9;
set<PII> P; map<int, LL> R, C; vector<pair<LL, int>> RR, CC;
int r[N], c[N], x[N];
int n;

int main() {

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

    RD(n); REP(i, n) {
        RD(r[i], c[i], x[i]);
        R[r[i]] += x[i];
        C[c[i]] += x[i];
        P.insert({r[i], c[i]});
    }

    for (auto r: R) RR.PB({r.se, r.fi});
    for (auto c: C) CC.PB({c.se, c.fi});
    SRT(RR); SRT(CC); RVS(RR); RVS(CC);

    LL z = 0; REP(i, n) checkMax(z, R[r[i]] + C[c[i]] - x[i]);

    REP(i, SZ(RR)) REP(j, SZ(CC)) {
        LL zz = RR[i].fi + CC[j].fi; if (zz <= z) break;
        if (!CTN(P, MP(RR[i].se, CC[j].se))) z = zz;
    }

    cout << z << endl;
}

Problem Ex. Sum of Min of Length

核心还是倍增祖先求出 x, y 两点之间的中点，然后还得根据 lca 的情况各种分类讨论。虽然之前我们学会了 dfs 序求 lca 这样的高级知识，但看起来这个题看起来避免不了倍增祖先，所以还是用倍增祖先求 lca 吧！

首先还是 dfs 各种预处理，这里还要需要两次 dfs，因为需要跑树形 dp 求出 dn[x] 和 up[x]，分别表示向下、向上的距离和。

根据路径的奇偶性，中点可能在两点之间也可能恰好落在某个点上。
对于那样的情况，它任意连向 x 或者 y 都可，但是这样讨论的话感觉情况有点多压力有点大…

于是我们需要设计一个子函数 ff(x, y)，表示求出所有到 x 的但不经过 y 的路径和！
这样的话无论如何我们都可以求两个分割点，避免讨论路径的奇偶性，而是只要处理一下两边深度一样的情况，压力大幅减轻！

最后只要考虑怎么求 ff(x, y)，有三种情况，无论哪一种我们都先加上 dn[x]+up[x]。
第一种是 x 是 y 的祖先，那么不仅要减去 dn[y]，并且 y 子树的所有点还要继续减去少算的距离，也就是 sz[y] * (dep[y]-dep[x])。
第二种是 y 是 x 的祖先，此时要先求出 y 一圈但不包含 x 所在分支的和，我们需要先求出 y 的孩子中是 x 祖先的节点 w，那么就是减去 dn[y]-dn[w]-sz[w]，然后再继续减去少算的，也就是 (LL)(n-sz[w]) * (dep[x]-dep[y])。
最后一种情况是有另一个 lca，这种情况可以合并到情况一，只要把距离函数改成 (dep[x]+dep[y]-2*dep[l]) 即可。

#include <lastweapon/io>
using namespace lastweapon;
const int N = int(2e5) + 9, LV = 20;
int fa[LV][N], dep[N], sz[N]; LL dn[N], up[N];
VI adj[N]; int n;

int move_up(int x, int d) {
    for (int lv=0;d;++lv,d>>=1)
        if (d&1) x = fa[lv][x];
    return x;
}
inline int lca(int x, int y) {
    if (dep[y] < dep[x]) swap(x, y); y = move_up(y, dep[y] - dep[x]); if (x == y) return x;
    DWN(lv, LV, 0) if (fa[lv][x] != fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
    return fa[0][x];
}
void dfs1(int u = 1, int p = 0) {
    sz[u] = 1;
    for (auto v: adj[u]) if (v != p) {
        dep[v] = dep[u] + 1;
        fa[0][v] = u; for (int lv=0;fa[lv+1][v]=fa[lv][fa[lv][v]];++lv);
        dfs1(v, u);
        sz[u] += sz[v];
        dn[u] += dn[v] + sz[v];
    }
}
void dfs2(int u = 1, int p = 0) {
    for (auto v: adj[u]) if (v != p) {
        up[v] = up[u] + dn[u] + n - dn[v] - 2*sz[v];
        dfs2(v, u);
    }
}
int sub(int u, int v) {
    return move_up(v, dep[v]-dep[u]-1);
}

LL ff(int x, int y) {
    // y
    // x
    // z    x
    //x y   y
    LL z = dn[x] + up[x]; int l = lca(x, y);
    if (l == y) {
        int w = sub(y, x);
        z -= up[y] + (dn[y] - dn[w] - sz[w]) + (LL)(n-sz[w])*(dep[x]-dep[y]);
    } else {
        z -= dn[y] + (LL)sz[y]*(dep[x]+dep[y]-2*dep[l]);
    }
    return z;
}

//    1
//  6 4 8
// 75 2
// 3

LL f(int a, int b) {

    if (a == b) return dn[a] + up[a];
    if (dep[a] < dep[b]) swap(a, b);
    int l = lca(a, b), d = dep[a] + dep[b] - 2*dep[l];
    int ma = move_up(a, d/2), mb = ma == l ? move_up(b, d/2-1) : fa[0][ma];
    LL z = ff(a, mb) + ff(b, ma);
    return z;
}

int main() {

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

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

    dfs1(); dfs2();

    Rush {
        int a, b; RD(a, b);
        printf("%lld\n", f(a, b));
    }
}

Posted by xiaodao
Category: 日常