如何将生成树重构为？

最小生成树 最小生成树为边权和最小的生成树 kruskal 贪心地，每次都加边权最小的边，如果这条边的两个端点已联通就不加 将两集合并入一个集合，查询两点是否在同一集合，用并查集维护 证明不会 重构树 当加入一条边时，建一个虚点当作这两点的父亲的父亲，点权为这条边的边权 重构树有重要性质：虚点点权从叶子到根非降或非升 P4768 [NOI2018] 归程 #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<vector> #define sf scanf #define pf printf #define mp make_pair #define fo(i,x,y) for(register int i = x;i<=y;++i) #define go(i,x,y) for(register int i = x;i>=y;--i) using namespace std; const int maxn = 200005; const int maxm = 400005; const int inf = 2147483647; const int mod = 1000000007; int T,n,m; struct node1{ int v,l,a; }; vector<node1> e1[maxn]; void add1(int u,int v,int l,int a){ e1[u].push_back(node1{v,l,a}); } int dis[maxn]; bool vis[maxn]; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q; struct node2{ int u,v,l,a; }e2[maxm]; bool cmp(node2 x,node2 y){ return x.a > y.a; } int fa[maxn+maxn]; int getf(int x){ return fa[x]<0?x:(fa[x]=getf(fa[x])); } int cnt_point; vector<int> e3[maxn+maxn]; void add3(int u,int v){ e3[u].push_back(v); } int stp[maxn+maxn][20],minv[maxn+maxn],dep[maxn+maxn],mind[maxn+maxn]; void clear_data(){ memset(vis,0,sizeof vis); memset(dis,0x3f,sizeof(dis)); dis[1] = 0; while(q.size()) q.pop(); fo(i,1,400000) fa[i] = -1; fo(i,1,400000) while(e3[i].size()) e3[i].pop_back(); fo(i,1,200000) while(e1[i].size()) e1[i].pop_back(); } void read(){ cin>>n>>m; fo(i,1,m){ int u,v,l,a; cin>>u>>v>>l>>a; e2[i].u = u,e2[i].v = v,e2[i].l = l,e2[i].a = a; add1(u,v,l,a),add1(v,u,l,a); } } void dij(){ fo(i,1,n) q.push(make_pair(dis[i],i)); while(q.size()){ pair<int,int> x = q.top(); q.pop(); int u = x.second,l = x.first; if(vis[u]) continue; vis[u] = true; for(node1 y:e1[u]){ int v = y.v,ll = y.l; if(dis[v] > l+ll){ dis[v]