前言：
教练给我们做铂金组的题目真的抬举我们了……
[USACO18OPEN] Disruption P
题目描述：
你有一棵节点数为 \(n\)，边数为 \(n-1\) 的树。然后你会给这棵树新增加 \(m\) 条边，对于每条边，有 \(u,v,w\) 分别表示边连接的两个节点分别为 \(u\) 和 \(v\)，和一个边权 \(w\)。每次删掉一条原树边，然后如果要使原图依旧联通，则需要添加的额外边的边权最小为多少。
数据范围：
\(1\leq N\leq 5\times 10^4,1\leq M\leq 5\times 10^4\)
思路：
我们发现，如果去枚举到底删掉的是那一条边，则去计算最小加的边的边权是不太方便处理的。那我们不如换一种思路：对于每一条边，他能对那些边造成贡献。如图：
我们如果添加了一条边权为 \(a\) 的边，则可能造成贡献的边就应该为蓝色的路径所覆盖的边。因此问题转换为求区间最值的问题。显然可以用树剖+线段树维护。
但是，我们依旧认为这个方法过于的无脑，没有思维含量 其实是我不会
显然的，我们可以将所有的非树边全部按照边权排序，显然的，每次遍历到的最小的边所能造成影响的路径中的边全都应为这个非树边的边权。证明也是比较显然的。
对于这样的一个操作，我们可以使用并查集来维护。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define mem(a) memset(a,0,sizeof(a))
#define set(a,b) memset(a,b,sizeof(a))
#define ls p<<1
#define rs p<<1|1
#define pb(x) push_back(x)
#define pt(x) putchar(x)
#define T int t;cin>>t;while(t--)
#define rand RAND
#define LOCAL
using namespace std;
char buf[1<<20],*p1,*p2;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
template<class Typ> Typ &re(Typ &x){char ch=gc(),sgn=0; x=0;for(;ch<'0'||ch>'9';ch=gc()) sgn|=ch=='-';for(;ch>='0'&&ch<='9';ch=gc()) x=x*10+(ch^48);return sgn&&(x=-x),x;}
template<class Typ> void wt(Typ x){if(x<0) putchar('-'),x=-x;if(x>9) wt(x/10);putchar(x%10^48);}
const int inf=0x3f3f3f3f3f;
const int maxn=50005;
const int mod=1e9+7;
int seed = 19243;
unsigned rand(){return seed=(seed*48271ll)%2147483647;}
void file(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);return;}
int n,m;
vector<pair<int,int>>G[maxn];
struct Ds{
int fa[maxn];
int find(int x){
if(x!=fa[x])return fa[x]=find(fa[x]);
return fa[x];
}
}ds;
int fa[maxn][20];
int g[maxn],Id[maxn],dep[maxn];
void dfs(int u,int f){
dep[u]=dep[f]+1;
fa[u][0]=f;
g[u]=f;
for(auto k:G[u]){
int v=k.first,id=k.second;
if(v==f)continue;
Id[v]=id;
dfs(v,u);
}
}
int ans[maxn];
struct node{
int u,v,w;
bool operator<(const node&x)const{
return w<x.w;
}
}E[maxn];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)ds.fa[i]=i;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
G[u].push_back({v,i});
G[v].push_back({u,i});
}
dfs(1,0);
for(int j=1;j<=18;j++){
for(int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
}
for(int i=1;i<=m;i++){
cin>>E[i].u>>E[i].v>>E[i].w;
}
sort(E+1,E+m+1);
memset(ans,-1,sizeof(ans));
for(int i=1;i<=m;i++){
for(int a=ds.find(E[i].u),b=ds.find(E[i].v);a!=b;){
if(dep[a]<dep[b])swap(a,b);
ds.fa[a]=ds.fa[g[a]];
ans[Id[a]]=E[i].w;
a=ds.find(a),b=ds.find(b);
}
}
for(int i=1;i<n;i++)cout<<ans[i]<<endl;
return 0;
}