luogu2195 HXY造公园 题解
我最喜欢的紫色水题(
给出一个森林,有两种操作。
- 询问某个点所在的树的直径
- 在两个点所在的两棵树间连一条边,最小化其直径
显然的,对于第一种操作,DP / DFS / BFS 预处理直径,并查集维护每棵树的点就行了。
问题在于高效维护第二种操作。
不难想到,两棵树之间连一条边,相当于合并两个集合。
而最小化新树的直径,显然要在两树直径的中点处连边。
证明:
反证法。若最优点不是直径中点,由于 直径有两个端点 且 树上两点有且仅有一条简单路径,若在非直径中点的 \(x\) 点连边,则当其接近直径一端时,直径另一端到达它的距离就大于到达直径中点的距离,反之则显然。这与假设不符,故原命题正确。
设从 \(x\) 与 \(y\) 之间连边,\(l(t)\) 为点 \(t\) 所在的树的直径。
则新树的直径只有三种可能。
- $ l(x)$
- \(l(y)\)
- $ + + 1$
合并后求最大值就行了。
#include<cstdio>
#include<iostream>
using namespace std;
const int N=3e5+6;
int n, m, q, ans, f[N], d[N], c[N];
int cnt, h[N], ver[N<<1], nxt[N<<1];
bool v[N];
int r_() {
int a=0; char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);a=(a<<1)+(a<<3)+(c^48),c=getchar());
return a;
}
void add(int x,int y) { ver[++cnt]=y, nxt[cnt]=h[x], h[x]=cnt; }
int get(int x) { return x==f[x]? x:f[x]=get(f[x]); }
void dp(int x,int fr) {
int i, y;
for(i=h[x];i;i=nxt[i]) if(ver[i]!=fr) {
y=ver[i], dp(y,x);
ans=max(ans,d[x]+d[y]+1), d[x]=max(d[x],d[y]+1);
}
}
void miku(int x) { ans=0, dp(x,0), c[x]=ans; }
int main() {
n=r_(), m=r_(), q=r_();
for(int i=1;i<=n;++i) f[i]=i;
for(int i=1,x,y,z;i<=m;++i) x=r_(), y=r_(), add(x,y), add(y,x), f[get(x)]=get(y);
for(int i=1;i<=n;++i) if(f[i]==i) miku(i);
while(q --> 0) {
int op=r_(), x=r_();
if(op&1) { printf("%d\n",c[get(x)]); continue; }
int y=r_();
x=get(x), y=get(y);
if(x==y) continue;
c[x]=max((c[x]+1)/2+(c[y]+1)/2+1,max(c[x],c[y]));
f[y]=x;
}
}
luogu2195 HXY造公园 题解
https://yozora0908.github.io/2021/lg2195-solution/