P4271 [USACO18FEB]New Barns P 题解

· · 题解

真不懂这题为啥要 LCT，虽然我一开始想的也是 LCT......

结论：一个点 u 在树内的最远点（之一），一定是这棵树的直径的一个端点。

另一个结论：两棵树用一条边连起来的时候，新的直径一定是两棵树各自的直径的两两组合中，最长的那一条。

考虑先离线建出整棵树，倍增维护 LCA，用公式 dist(u,v)=depth_u+depth_v-2 \times depth_{lca(u,v)} 计算两点间距离。

然后按顺序操作，碰到 \texttt{B} 加边操作，合并两棵树，并且我们发现其中一棵只有一个点，那么上面说的四个点两两组合，可以简化为 3 种组合方式，选出距离最大的一种作为新的直径并记录。

碰到 \texttt{Q} 查询操作，直接找到 k 点所在的树的直径，然后分别算出 k 到直径两个端点距离，取较大值即可。

再考虑如何记录直径，我一开始想的是用并查集，把一条直径记录在并查集的代表元的位置。后来想想并查集都不用了，离线建树的过程中，直接求出每个点所在的树的根，把直径记录在根的位置就行了，还省掉了并查集的常数。

时间复杂度：假设操作数是 q，结点数是 n，如果倍增，预处理复杂度 O(n \log n)，单次求 lca 复杂度 O(\log n)，总复杂度约为 O((n+q)\log n)；用欧拉序列 + ST 表求 lca 的总复杂度 O(n \log n + q)，再用四毛子优化就可以做到线性了。

具体细节看代码吧：

#include <cstdio>
using namespace std;
const int N = 100010;
const int LOGN = 17;
struct Edge {
    int to, nxt;
}edges[N];
int point[N][2]; //记录直径的两个端点
int fa[N][LOGN], depth[N];
int opt[N], queryu[N], idx[N];
int head[N], root[N], n, m, nedge; //root[u] 表示 u 点所在的树的根
inline int max(int x, int y) {return x > y ? x : y;}
inline void swap(int &x, int &y) {x ^= y; y ^= x; x ^= y;}
inline void addedge(int u, int v) {
    edges[++nedge].to = v;
    edges[nedge].nxt = head[u];
    head[u] = nedge;
}
inline void dfs(int u) {
    for(register int i = 1; (1 << i) <= depth[u]; ++i)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(register int i = head[u]; i; i = edges[i].nxt) {
        int v = edges[i].to;
        fa[v][0] = u; depth[v] = depth[u] + 1;
        if(u == 0) root[v] = v;
        else root[v] = root[u];
        dfs(v);
    }
}
inline int LCA(int u, int v) {
    if(depth[u] < depth[v]) swap(u, v);
    for(register int i = LOGN - 1; i >= 0; --i)
        if((1 << i) <= depth[u] - depth[v]) u = fa[u][i];
    if(u == v) return u;
    for(register int i = LOGN - 1; i >= 0; --i)
        if(fa[u][i] != fa[v][i]) {u = fa[u][i]; v = fa[v][i];}
    return fa[u][0];
}
inline int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[LCA(u, v)];
}
int main() {
    scanf("%d", &m);
    for(register int i = 1; i <= m; ++i) {
        char op[5];
        scanf("%s %d", op, &queryu[i]);
        if(op[0] == 'B') opt[i] = 1; else opt[i] = 2;
        if(opt[i] == 1) {idx[i] = ++n; addedge(queryu[i] > -1 ? queryu[i] : 0, n);} //idx[i] 记录第 i 步（如果是 B 操作）新建的点的编号
    }
    dfs(0);
    for(register int u = 1; u <= n; ++u) point[u][0] = point[u][1] = u;
    for(register int i = 1; i <= m; ++i) {
        if(opt[i] == 1 && queryu[i] != -1) {
            int x = root[queryu[i]];
            int dist1 = dist(point[x][0], point[x][1]);
            int dist2 = dist(point[x][0], idx[i]), dist3 = dist(point[x][1], idx[i]);
            if(dist1 >= dist2 && dist1 >= dist3) {}
            else if(dist2 >= dist1 && dist2 >= dist3) point[x][1] = idx[i];
            else point[x][0] = idx[i]; //三个距离选最大的记录下来（注意以上的 >= 不能写成 >，具体原因自行思考）
        }
        if(opt[i] == 2) {
            int x = root[queryu[i]];
            printf("%d\n", max(dist(point[x][0], queryu[i]), dist(point[x][1], queryu[i])));
        }
    }
    return 0;
}