#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ar array
const int mxN=1e5;
int n, a[mxN], r[mxN];
struct tree {
int d[mxN], anc[mxN][17], anc2[mxN][17], b1[mxN][17], b2[mxN][17];
vector<ar<int, 2>> adj[mxN];
int find(int x) {
return x^r[x]?r[x]=find(r[x]):x;
// return x^r[x]?find(r[x]):x;
}
void dfs2(int u, int w) {
// /*
a[u]=min(w, a[u]);
for(int v : adj2[u])
dfs2(v, w);
adj2[u].clear();
// */
// a[u]=min(w, a[u]);
// for(auto v : adj[u])
// if(v[1]^p)
// dfs2(v[1], w, u);
}
bool join(int x, int y, int w) {
if((x=find(x))==(y=find(y)))
return 0;
r[x]=y;
if(a[y]<=1e9)
dfs2(x, w);
if(a[x]<=1e9)
dfs2(y, w);
adj2[y].push_back(x);
return 1;
}
vector<ar<int, 3>> co(vector<ar<int, 3>> e) {
iota(r, r+n, 0);
vector<ar<int, 3>> g;
for(auto f : e) {
if(join(f[1], f[2], f[0])) {
adj[f[1]].push_back({f[0], f[2]});
adj[f[2]].push_back({f[0], f[1]});
if(adj[f[1]].size()>2||adj[f[2]].size()>2)
dfs2(find(f[1]), f[0]);
} else
// g.push_back(f);
dfs2(find(f[1]), f[0]);
}
memset(b2, 0x3f, sizeof(b2));
return g;
}
int gv(int u, int x, int y) {
int r=a[u];
for(auto e : adj[u]) {
if(e[1]^x&&e[1]^y) {
r=min(e[0], r);
break;
}
}
return r;
}
void dfs(int u=0, int p=-1) {
anc[u][0]=p;
anc2[u][0]=u;
for(int i=1; i<17; ++i) {
anc[u][i]=~anc[u][i-1]?anc[anc[u][i-1]][i-1]:-1;
anc2[u][i]=~anc[u][i-1]?anc2[anc[u][i-1]][i-1]:0;
b1[u][i]=~anc[u][i-1]?max(b1[u][i-1], b1[anc[u][i-1]][i-1]):0;
}
if(u) {
b2[u][1]=gv(p, u, anc[p][0]);
for(int i=2; i<17; ++i)
b2[u][2]=~anc[u][i-1]?min({b2[u][i-1], b2[anc[u][i-1]][i-1], gv(anc[u][i-1], anc2[u][i-1], anc[anc[u][i-1]][0])}):0;
}
for(auto v : adj[u]) {
if(v[1]^p) {
b1[v[1]][0]=v[0];
d[v[1]]=d[u]+1;
dfs(v[1], u);
}
}
}
int qry(int x, int y) {
if(d[x]<d[y])
swap(x, y);
int r=0;
for(int i=16; ~i; --i) {
if(d[x]-(1<<i)>=d[y]) {
r=max(b1[x][i], r);
x=anc[x][i];
}
}
if(x==y)
return r;
for(int i=16; ~i; --i) {
if(anc[x][i]^anc[y][i]) {
r=max({b1[x][i], b1[y][i], r});
x=anc[x][i];
y=anc[y][i];
}
}
return max({b1[x][0], b1[y][0], r});
}
int qry2(int x, int y) {
if(d[x]<d[y])
swap(x, y);
int r=2e9, x2=x, y2=y;
for(int i=16; ~i; --i) {
if(d[x]-(1<<i)>=d[y]) {
if(x2^x)
r=min(gv(x, x2, anc[x][0]), r);
r=min(b2[x][i], r);
x2=anc2[x][i];
x=anc[x][i];
}
}
if(x==y)
return r;
for(int i=16; ~i; --i) {
if(anc[x][i]^anc[y][i]) {
if(x2^x)
r=min(gv(x, x2, anc[x][0]), r);
if(y2^y)
r=min(gv(y, y2, anc[y][0]), r);
r=min({b2[x][i], b2[y][i], r});
x2=anc2[x][i];
y2=anc2[y][i];
x=anc[x][i];
y=anc[y][i];
}
}
if(x2^x)
r=min(gv(x, x2, anc[x][0]), r);
if(y2^y)
r=min(gv(y, y2, anc[y][0]), r);
return min(gv(anc[x][0], x, y), r);
}
} t0;//, t1;
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
::n=n;
vector<ar<int, 3>> e;
for(int i=0; i<m; ++i)
e.push_back({w[i], u[i], v[i]});
sort(e.begin(), e.end());
memset(a, 0x3f, 4*n);
e=t0.co(e);
/*t1.co(e);
for(auto f : e) {
a[f[1]]=max(f[0], a[f[1]]);
a[f[2]]=max(f[0], a[f[2]]);
}*/
t0.dfs();
//t1.dfs();
}
int getMinimumFuelCapacity(int x, int y) {
// cout << t0.qry(x, y) << " " << t0.qry2(x, y) << " " << t1.qry(x, y) << endl;
// int a=min(max(t0.qry(x, y), t0.qry2(x, y)), t1.qry(x, y));
int b=max(t0.qry(x, y), a[x]);
return b>1e9?-1:b;
}
Compilation message
swap.cpp: In member function 'void tree::dfs2(int, int)':
swap.cpp:20:15: error: 'adj2' was not declared in this scope; did you mean 'adj'?
20 | for(int v : adj2[u])
| ^~~~
| adj
swap.cpp:22:3: error: 'adj2' was not declared in this scope; did you mean 'adj'?
22 | adj2[u].clear();
| ^~~~
| adj
swap.cpp: In member function 'bool tree::join(int, int, int)':
swap.cpp:37:3: error: 'adj2' was not declared in this scope; did you mean 'adj'?
37 | adj2[y].push_back(x);
| ^~~~
| adj
