题解：CF1648E Air Reform
fish_love_cat · · 题解
虚空思考一早上试图优化暴力，结果发现复杂度分析错了这个是正解，严肃浪费 4h /hec
显然考虑 kruskal 重构树。
对于给定的图按最小生成树的方式建一遍重构树，于是补图边权转化成树上的 LCA。
我们要求的问题就是对于每一条边，两个端点在补图上的瓶颈路。
一样考虑对补图跑一个重构树。
边太多了不能直接建，考虑优化建图。
回到 kruskal 的过程，我们按照边权从小往大进行枚举，而这里边权是原来树上的 LCA。
所以我们考虑自底向上枚举树上的点，以其作为 LCA 时的边思考怎么进行加入。
首先底下的边加完以后变成若干个连通块分别划分在左右两侧，此时你可以对左右两侧的连通块进行连边。
考虑怎么合并连通块。
很容易得到一个暴力合并的做法，选择两个连通块，遍历内部的所有点对，如果原图存在边则不管，否则合并连通块然后退出。
这么做的时间复杂度是？
合并
无法合并最多
这个暴力是线性的！
然后做完了啊，合并连通块集合直接 dsu 处理即可。
时间复杂度应该是
注意不要写退化。
Upd：原先贴的代码是经验的代码，本题需要卡常故严肃更换。
然后 umap 被卡了但是 map 过了，我寻思搬 OOI 的题 CF 怎么还有 hack 啊（
下面的代码是 map。
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define int long long
#define N 200005
struct IO {
static const int inSZ = 1 << 17;
char inBuf[inSZ], *in1, *in2;
template<class T> inline __attribute((always_inline))
T read() {
if (in1 > inBuf + inSZ - 32) [[unlikely]] {
auto len = in2 - in1;
memcpy(inBuf, in1, len);
in1 = inBuf, in2 = inBuf + len;
in2 += fread(in2, 1, inSZ - len, stdin);
if (in2 != inBuf + inSZ) *in2 = 0;
}
T res = 0;
unsigned char c;
bool neg = 0;
while ((c = *in1++) < 48) neg = c == 45;
while (res = res * 10 + (c - 48), (c = *in1++) >= 48);
return neg ? -res : res;
}
static const int outSZ = 1 << 21;
char outBuf[outSZ], *out;
template<class T> inline __attribute((always_inline))
void write(T x) {
if (out > outBuf + outSZ - 32) [[unlikely]]
{
fwrite(outBuf, 1, out - outBuf, stdout), out = outBuf;
}
if (!x) return *out++ = 48, void();
if (x < 0) *out++ = 45, x = -x;
alignas(2) const char* digits =
"0001020304050607080910111213141516171819"
"2021222324252627282930313233343536373839"
"4041424344454647484950515253545556575859"
"6061626364656667686970717273747576777879"
"8081828384858687888990919293949596979899";
alignas(64) static char buf[20];
char* p = buf + 20;
while (x >= 10) memcpy(p -= 2, digits + x % 100 * 2, 2), x /= 100;
if (x) *--p = 48 + x;
auto len = buf + 20 - p;
memcpy(out, p, len), out += len;
}
void init() {
in1 = in2 = inBuf + inSZ;
out = outBuf;
}
~IO() { fwrite(outBuf, 1, out - outBuf, stdout); }
} IO;
template<class T = int> inline T read() {
return IO.read<T>();
}
template<class T> inline void print(T x, char c) {
IO.write(x), *IO.out++ = c;
}
template<class T> inline void print(T x) {
IO.write(x);
}
inline __attribute((always_inline)) void printCh(char c) {
*IO.out++ = c;
}
using namespace std;
struct vec{
int u,v,w;
};
vector<vec>vct,vct2;
bool cmp(vec a,vec b){
return a.w<b.w;
}
map<int,bool>mp;
int fa[N<<1];
int v[N<<1];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void initdsu(int n){
for(int i=1;i<=n;i++)
fa[i]=i;
}
vector<int>ve[N<<1];
vector<int>e[N];
vector<int>d[N];
bool del[N];
int fa2[N];
int ver[N];
int vs=114;
void down(int x){
if(ver[x]==vs)return;
ver[x]=vs;
fa2[x]=fa[x];
}
int find2(int x){
down(x);
return fa2[x]==x?x:fa2[x]=find2(fa2[x]);
}
void merge(int x,int y){
x=find2(x),y=find2(y);
if(x==y)return;
if(d[x].size()>d[y].size())swap(x,y);
for(int i:d[x])d[y].push_back(i);
del[x]=1;
fa2[x]=y;
}
int qwq[N<<1];
void dfs(int X){
if(ve[X].empty()){
qwq[X]=X;
return;
}
for(int i:ve[X])
dfs(i);
vector<pair<int,int>>add;
vs++;
for(int x:e[qwq[ve[X][0]]]){
if(!del[x])
for(int y:e[qwq[ve[X][1]]])
if(!del[y]&&find2(x)!=find2(y))
for(int i:d[x]){
bool flg=0;
for(int j:d[y])
if(!mp[(i<<30)|j]){
flg=1;
fa2[find2(x)]=find2(y);
vct2.push_back({i,j,-1});
add.push_back({x,y});
break;
}
if(flg)break;
}
}
vs++;
for(pair<int,int>o:add)
merge(o.first,o.second);
int x=qwq[ve[X][0]];
int y=qwq[ve[X][1]];
if(e[x].size()>e[y].size())swap(x,y);
qwq[X]=y;
for(int i:e[x])
if(!del[i])
e[y].push_back(i);
}
int mi[25][N<<1];
int dfn[N<<1],dfnn;
int get(int u,int v){
if(dfn[u]<dfn[v])return u;
return v;
}
void dfsiz(int x,int fa){
dfn[x]=++dfnn;
mi[0][dfn[x]]=fa;
for(int i:ve[x])
dfsiz(i,x);
}
int lg[N<<1];
int lca(int u,int v){
if(u==v)return u;
u=dfn[u],v=dfn[v];
if(u>v)swap(u,v);
int g=lg[v-u];
return get(mi[g][u+1],mi[g][v-(1<<(g))+1]);
}
struct fish{
int u,v;
};
vector<fish>q;
void init(int n){
dfnn=0;
vct.clear();
vct2.clear();
mp.clear();
initdsu(n<<1);
for(int i=1;i<=(n<<1);i++)
ve[i].clear(),v[i]=0;
for(int i=1;i<=n;i++)
e[i].clear(),d[i].clear();
for(int i=1;i<=n;i++)
e[i].push_back(i),
d[i].push_back(i),
del[i]=0;
}
void solve(){
q.clear();
int n=read(),m=read();
int in_n=n;
init(n);
for(int i=1;i<=m;i++){
int u=read(),v=read(),w=read();
vct.push_back({u,v,w});
mp[(u<<30)|v]=mp[(v<<30)|u]=1;
q.push_back({u,v});
}
sort(vct.begin(),vct.end(),cmp);
for(vec i:vct){
if(find(i.u)==find(i.v))continue;
i.u=find(i.u);
i.v=find(i.v);
n++;
fa[i.u]=n;
fa[i.v]=n;
ve[n].push_back(i.u);
ve[n].push_back(i.v);
v[n]=i.w;
}
initdsu(n);
dfs(n);
dfsiz(n,0);
for(int i=1;i<=20;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
mi[i][j]=get(mi[i-1][j],mi[i-1][j+(1<<(i-1))]);
for(int i=0;i<vct2.size();i++)
vct2[i].w=v[lca(vct2[i].u,vct2[i].v)];
sort(vct2.begin(),vct2.end(),cmp);
initdsu(n);
n=in_n;
for(int i=1;i<=(n<<1);i++)
ve[i].clear(),v[i]=0;
for(vec i:vct2){
if(find(i.u)==find(i.v))continue;
i.u=find(i.u);
i.v=find(i.v);
n++;
fa[i.u]=n;
fa[i.v]=n;
ve[n].push_back(i.u);
ve[n].push_back(i.v);
v[n]=i.w;
}
dfnn=0;
dfsiz(n,0);
for(int i=1;i<=20;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
mi[i][j]=get(mi[i-1][j],mi[i-1][j+(1<<(i-1))]);
for(fish i:q)
print(v[lca(i.u,i.v)],' ');
}
signed main(){
for(int i=2;i<=(N<<1)-3;i<<=1)lg[i]++;
for(int i=1;i<=(N<<1)-3;i++)lg[i]+=lg[i-1];
IO.init();
int t=read();
while(t--)solve();
return 0;
}
//「好久不见。你还是老样子嘛，完全不管对方的意愿，就这样热情地紧逼过来──」
// 咬破的嘴唇滴下了鲜血。
//「可是啊，不好意思，出于女人的意志这个因素，我是不会像上次一样那么简单地就任你掌控的。想要我的心的话，就给我做好打持久战的觉悟吧，莫乌尔涅──」
// 失去焦点的眼神望向前方的黑暗，她脸上浮现出颤抖的笑容。
//「──不，是〈织光的第十四兽【Vincula】〉──！」