题解：P10866 [HBCPC2024] Colorful Tree
xiezheyuan
·
·
题解
简要题意
你需要维护一个 n 个点的树，初始时所有点都是白色。有 m 次操作，每次操作给定一条树上简单路径，你需要将路径上所有点染成黑色。
你需要求出最长的同色路径（注意路径上所有点都必须同色，路径长度定义为这条路径上点的数量，包含端点）。
## 思路
本来以为是路径端点颜色相同，我还以为是经典题目，写完后测了样例发现不对，这才发现题目要求是路径上所有点的颜色……不过这道题也不难。
首先我们先分开求最长黑色路径和最长白色路径，先求最长黑色路径。一种经典的错误思路是维护黑色 / 白色点集，直接维护点集直径。由于黑色 / 白色点**不一定**构成一个连通块，所以求出来的直径中间可能会夹杂其他颜色的点。
顺着这个思路想，我们可以就维护同色连通块，然后维护这个连通块的直径。维护连通块的首选是并查集。我们可以将直径信息存在并查集的根节点上。但是染色可能会出现一条链染多次的情况。
由于我没有想到这玩意也可以并查集，所以我用到了一个比较劣的方法，我们维护一个点第一个被染成黑色的时刻，显然这个可以离线后倒序枚举询问转换为树上染颜色，可以用重链剖分配合颜色段均摊简单维护。
然后我们按照第一个被染成黑色的时刻顺序依次考虑每一个点，先暴力枚举这个点直接相邻的其他点，如果这个点同样也是黑色点，且还没有和这个点合并为一个连通块，那么我们就可以直接合并，合并并查集的同时也要合并直径信息，在更新直径信息的时候更新当前时刻最大直径。注意这样得到的答案需要做一遍前缀最大值才是真的答案（因为答案显然单调，且可能会有其他连通块未被统计）。
对于最长白色路径，如果按照时间顺序做就是删点，比较难做，我们离线倒着做，就变成了加点，和上面做法几乎一样，就不提了。
至于直径合并，这是经典 trick，两个点集的直径端点，一共四个，我们选出两个点，使得这两个点构成的路径长度最大，这个最长路径就是两个点集的并的直径。
最后将两种答案取 $\max$ 即可，时间复杂度单组数据 $O(n\log n+m\log^2 n)$。瓶颈在重链剖分配合颜色段均摊。
## 代码
5.04 KB 大常数代码，建议不要学。
```cpp
#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
```