2024浙江省赛 J. Even or Odd Spanning Tree

一道对次小生成树的考察，首先我们可以确定的是最小生成树肯定是其中一个答案，现在假设最小生成树的权值和 $cost(T)$ 是奇数,那么我们只要求偶数的答案即可，最小的偶数权值和 $cost(T^{\prime })$ 我们知道一定比 $cost(T)$ 大，那我们自然可以想到求严格次小生成树，但是求严格次小生成树只能保证一定比 $cost(T)$ 大，但是不能保证是偶数。我们回顾一下次小生成树的求法，考虑加入 $x-y$ 这一条边，会构成一个环，我们选取最小生成树上 $x-y$ 路径上权值最大的一条边，替换它，更新答案(如果要求严格的话这一步可能求出来的和最小生成树一样，那就要维护次大边，替换次大边) ,为了保证是偶数，我们不妨分开维护奇数和偶数，分别维护 $x-y$ 路径上奇数边权的最大和次大边，偶数边权的最大和次大边，那么每次尝试替换的时候，如果这条边是奇数，我就去查询最小生成树上偶数边权的最大和次大，偶数同理，那么本题即可解决.
这题还有一个corner case，有可能没有次小生成树或者最小生成树

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;
#define int long longconstexpr int maxn = 5e5+10;
constexpr i64 inf = 1e18;
template <typename T>struct Edge{int u,v;T w;Edge()=default;Edge(int u,int v,T w):u(u),v(v),w(w){}bool operator<(const Edge &other)const{return w<other.w;}  
};
using edge = Edge<i64>;static constexpr int LOG = 22;
static constexpr int NEG_INF = numeric_limits<int>::min();class Tr {
private:struct Edge {int to, nxt, val;};vector<Edge> e;vector<int> head;int cnt;vector<array<int, LOG>> fa;vector<int> dep;// 到祖先的路径上边权最大的边vector<array<array<int,2>, LOG>> max1;// 到祖先的路径上边权次大的边，若不存在则为 -INFvector<array<array<int,2>, LOG>> max2;public:// 构造函数：传入节点数 n，初始化各个数组的大小和默认值Tr(int n): head(n+1, -1), dep(n+1, 0), fa(n+1), max1(n+1), max2(n+1), cnt(0) {e.reserve(2 * n);for (int i = 0; i <= n; ++i) {for (int j = 0; j < LOG; ++j) {fa[i][j]   = 0;max1[i][j][0] = max1[i][j][1] = NEG_INF;max2[i][j][0] = max2[i][j][1] = NEG_INF;}}}// 添加有向边void addedge(int u, int v, int val) {e.push_back({v, head[u], val});head[u] = cnt++;}// 添加无向边void insertedge(int u, int v, int val) {addedge(u, v, val);addedge(v, u, val);}// DFS 预处理深度、祖先和最大边权void dfs(int x, int parent) {dep[x] = dep[parent] + 1;fa[x][0] = parent;max2[x][0][0] = NEG_INF;max2[x][0][1] = NEG_INF;for (int i = 1; (1 << i) <= dep[x]; ++i) {int p = fa[x][i - 1];fa[x][i] = fa[p][i - 1];array<int, 4> kk = { max1[x][i - 1][0], max1[p][i - 1][0], max2[x][i - 1][0], max2[p][i - 1][0] };sort(kk.begin(), kk.end());max1[x][i][0] = kk[3];int ptr = 2;while (ptr >= 0 && kk[ptr] == kk[3]) --ptr;max2[x][i][0] = (ptr >= 0 ? kk[ptr] : NEG_INF);kk = { max1[x][i - 1][1], max1[p][i - 1][1], max2[x][i - 1][1], max2[p][i - 1][1] };sort(kk.begin(),kk.end());max1[x][i][1] = kk[3];ptr=2;while(ptr>=0&&kk[ptr]==kk[3])--ptr;max2[x][i][1] = (ptr>=0?kk[ptr]:NEG_INF);}for (int idx = head[x]; idx != -1; idx = e[idx].nxt) {int to = e[idx].to;if (to == parent) continue;max1[to][0][e[idx].val&1] = e[idx].val;dfs(to, x);}}// 求最近公共祖先int lca(int a, int b) const {if (dep[a] < dep[b]) swap(a, b);for (int i = LOG - 1; i >= 0; --i) {if (dep[a] - (1 << i) >= dep[b]) a = fa[a][i];}if (a == b) return a;for (int i = LOG - 1; i >= 0; --i) {if (fa[a][i] != fa[b][i]) {a = fa[a][i];b = fa[b][i];}}return fa[a][0];}// 查询从 a 到 ancestor 路径上最大的边权（排除值为 val 的边）int query(int a, int ancestor, int val,int k) const {int res = NEG_INF;int diff = dep[a] - dep[ancestor];for (int i = LOG - 1; i >= 0; --i) {if (diff & (1 << i)) {if (max1[a][i][k] != val) res = max(res, max1[a][i][k]);else                res = max(res, max2[a][i][k]);a = fa[a][i];}}return res;}
};edge e[maxn];
bool use[maxn];
int fa[maxn],n,m;
i64 sum = 0;;
int find(int x){return x==fa[x]?x:fa[x] = find(fa[x]);
}
bool merge(int x,int y){int fx = find(fa[x]),fy = find(fa[y]);if(fx==fy) return 0;fa[fy] = fx;return 1;
}bool kruskal(Tr &tr){sort(e+1,e+m+1);int c = 0;for(int i = 1;i<=n;++i) fa[i]=i;for(int i = 1;i<=m;++i){if(merge(e[i].u,e[i].v)){sum+=e[i].w;use[i]=true;tr.insertedge(e[i].u,e[i].v,e[i].w);++c;}}return c==n-1;
}void solve(){cin>>n>>m;sum = 0;for(int i = 1;i<=m;++i){use[i]=0;int u,v,w;cin>>u>>v>>w;e[i] = Edge(u,v,(i64)w);}Tr tr(n+100);bool flag =kruskal(tr);array<i64,2> ANS={{inf,inf}};if(flag==0){cout<<-1<<" "<<-1<<"\n";return;}ANS[sum&1] = sum;int kk = (sum&1)^1;i64 ans = inf;tr.dfs(1,0);for(int i = 1;i<=m;++i){if(!use[i]){int lca = tr.lca(e[i].u,e[i].v);int sx = e[i].w&1;i64 tmpa = tr.query(e[i].u,lca,e[i].w,sx^1);i64 tmpb = tr.query(e[i].v,lca,e[i].w,sx^1);if(max(tmpa,tmpb)>0){ANS[kk] = min(ANS[kk],sum-max(tmpa,tmpb)+e[i].w);}}}cout<<(ANS[0]==inf?-1:ANS[0])<<" "<<(ANS[1]==inf?-1:ANS[1])<<"\n";
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int t=1;cin>>t;while(t--) solve();return 0;
}