自动搬运

查看原文

来自洛谷，原作者为

	xiezheyuan 明明我已昼夜无间踏尽前路/梦想中的彼岸为何还未到/明明我已奋力无间/天天上路/我不死也为活更好/快要到终点才能知道/又再回到起点重头上路

搬运于2025-08-24 23:02:00，当前版本为作者最后更新于2024-08-14 15:24:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简要题意

你需要维护一个 $n$ 个点的树，初始时所有点都是白色。有 $m$ 次操作，每次操作给定一条树上简单路径，你需要将路径上所有点染成黑色。

你需要求出最长的同色路径（注意路径上所有点都必须同色，路径长度定义为这条路径上点的数量，包含端点）。

$T$ 组数据。$1\leq \sum n,\sum m\leq 2\times10^5$。

思路

本来以为是路径端点颜色相同，我还以为是经典题目，写完后测了样例发现不对，这才发现题目要求是路径上所有点的颜色……不过这道题也不难。

首先我们先分开求最长黑色路径和最长白色路径，先求最长黑色路径。一种经典的错误思路是维护黑色 / 白色点集，直接维护点集直径。由于黑色 / 白色点不一定构成一个连通块，所以求出来的直径中间可能会夹杂其他颜色的点。

顺着这个思路想，我们可以就维护同色连通块，然后维护这个连通块的直径。维护连通块的首选是并查集。我们可以将直径信息存在并查集的根节点上。但是染色可能会出现一条链染多次的情况。

由于我没有想到这玩意也可以并查集，所以我用到了一个比较劣的方法，我们维护一个点第一个被染成黑色的时刻，显然这个可以离线后倒序枚举询问转换为树上染颜色，可以用重链剖分配合颜色段均摊简单维护。

然后我们按照第一个被染成黑色的时刻顺序依次考虑每一个点，先暴力枚举这个点直接相邻的其他点，如果这个点同样也是黑色点，且还没有和这个点合并为一个连通块，那么我们就可以直接合并，合并并查集的同时也要合并直径信息，在更新直径信息的时候更新当前时刻最大直径。注意这样得到的答案需要做一遍前缀最大值才是真的答案（因为答案显然单调，且可能会有其他连通块未被统计）。

对于最长白色路径，如果按照时间顺序做就是删点，比较难做，我们离线倒着做，就变成了加点，和上面做法几乎一样，就不提了。

至于直径合并，这是经典 trick，两个点集的直径端点，一共四个，我们选出两个点，使得这两个点构成的路径长度最大，这个最长路径就是两个点集的并的直径。

最后将两种答案取 $\max$ 即可，时间复杂度单组数据 $O(n\log n+m\log^2 n)$。瓶颈在重链剖分配合颜色段均摊。

代码

5.04 KB 大常数代码，建议不要学。

#include <bits/stdc++.h>
//#define int long long
using namespace std;

const int N = 2e5 + 5;

namespace odt{
    struct node{
        int l,r;
        mutable int v;
        node(int L, int R, int V){l = L, r = R, v = V;}
        bool operator<(const node &x) const {return l < x.l;}
    };
    set<node> tree;
    auto split(int pos){
        auto it = tree.lower_bound(node(pos, 0, 0));
        if(it != tree.end() && it -> l == pos) return it;
        it--;
        int l = it -> l, r = it -> r, v = it -> v;
        tree.erase(it);
        tree.insert(node(l, pos - 1, v));
        return tree.insert(node(pos, r, v)).first;
    }
    void assign(int l, int r, int v){
        auto R = split(r + 1), L = split(l);
        tree.erase(L, R);
        tree.insert(node(l, r, v));
    }
    int query(int l, int r){
        auto R = split(r + 1), L = split(l);
        for(auto it = L;it != R;it++){
            return it -> v;
        }
    }
}

struct edge{
    int nxt, to;
} g[N << 1];
int head[N], ec;

void add(int u, int v){
    g[++ec].nxt = head[u];
    g[ec].to = v;
    head[u] = ec;
}

int dep[N], siz[N], father[N], son[N], top[N], seg[N], rev[N];

void dfs1(int u,int fa){
    siz[u] = 1;father[u] = fa;
    dep[u] = dep[fa] + 1;
    for(int i=head[u];i;i=g[i].nxt){
        int v = g[i].to;
        if(v == fa) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}

void dfs2(int u,int fa){
    if(son[u]){
        top[son[u]] = top[u];
        seg[son[u]] = (++seg[0]);
        rev[seg[0]] = son[u];
        dfs2(son[u], u);
    }
    for(int i=head[u];i;i=g[i].nxt){
        int v = g[i].to;
        if(v == fa || son[u] == v) continue;
        top[v] = v;
        seg[v] = (++seg[0]);
        rev[seg[0]] = v;
        dfs2(v, u);
    }
}

int lca(int x, int y){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = father[top[x]];
    }
    return dep[x] > dep[y] ? y : x;
}

void UpdateTree(int x,int y,int z){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        odt::assign(seg[top[x]], seg[x], z);
        x = father[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    odt::assign(seg[x], seg[y], z);
}

int dis(int x, int y){
    int b = lca(x, y);
    int a = dep[x] + dep[y] - 2 * dep[b] + 1;
    return a;
}

int fa[N];

int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int n, m;
struct option{
    int x, y;
} opt[N];
bool col[N];
int black[N], white[N];

struct diameter{
    int x, y;
} d[N];

diameter operator+(const diameter& x, const diameter& y){
    auto _ = [&](int x, int y){
        return make_pair(dis(x, y), make_pair(x, y));
    };
    vector<pair<int,pair<int,int> > > bkt = {
        _(x.x, x.y), _(y.x, y.y),
        _(x.x, y.x), _(x.y, y.y),
        _(x.x, y.y), _(x.y, y.x)
    };
    auto ret = *max_element(bkt.begin(), bkt.end());
    return {ret.second.first, ret.second.second};
}

void solve(){
    cin >> n >> m;
    for(int i=1;i<=n;i++) fa[i] = i;
    for(int i=1;i<n;i++){
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    seg[0] = seg[1] = 1;
    top[1] = rev[1] = 1;
    dfs1(1, 0);dfs2(1, 0);
    odt::tree.clear();
    odt::tree.insert(odt::node(1, n, m + 1));
    for(int i=1;i<=m;i++){
        cin >> opt[i].x >> opt[i].y;
    }
    for(int i=m;i>=1;i--) UpdateTree(opt[i].x, opt[i].y, i);
    vector<pair<int,int> > vp;
    for(int i=1;i<=n;i++){
        int tim = odt::query(seg[i], seg[i]);
        vp.push_back({tim, i});
    }
    sort(vp.begin(), vp.end());
    for(auto& [tim, u] : vp){
        if(tim > m) continue;
        col[u] = 1;
        d[u] = {u, u};
        for(int i=head[u];i;i=g[i].nxt){
            int v = g[i].to;
            if(!col[v]) continue;
            if(find(u) != find(v)){
                d[find(u)] = d[find(u)] + d[find(v)];
                black[tim] = max(black[tim], dis(d[find(u)].x, d[find(u)].y));
                fa[find(v)] = find(u);
            }
        }
    }
    for(int i=1;i<=m;i++) black[i] = max(black[i], black[i - 1]);
    reverse(vp.begin(), vp.end());
    for(int i=1;i<=n;i++) fa[i] = i, col[i] = 0;
    for(auto& [tim, u] : vp){
        col[u] = 1;
        d[u] = {u, u};
        for(int i=head[u];i;i=g[i].nxt){
            int v = g[i].to;
            if(!col[v]) continue;
            if(find(u) != find(v)){
                d[find(u)] = d[find(u)] + d[find(v)];
                white[tim - 1] = max(white[tim - 1], dis(d[find(u)].x, d[find(u)].y));
                fa[find(v)] = find(u);
            }
        }
    }
    for(int i=m-1;i;i--) white[i] = max(white[i], white[i + 1]);
    for(int i=1;i<=m;i++) cout << max(black[i], white[i]) << '\n';
}

void clear(){
    for(int i=1;i<=n;i++){
        head[i] = dep[i] = siz[i] = father[i] = son[i] = top[i] = seg[i] = rev[i] = 0;
    }
    for(int i=1;i<=m;i++){
        white[i] = black[i] = col[i] = 0;
    }
    ec = 0;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t; cin >> t;
    while(t--) solve(), clear();
    return 0;
}

// Written by xiezheyuan