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));
}
}
