What if you are given a tree, not a graph, how do you solve it?

Building mst by the edges with a maximum width and considering the edges on this mst is enough.

What edges in the tree will be broken first?

Consider the edge with a minimum width in a tree, there are two approaches. You can either collect everything from one subtree and go to another subtree or vice versa. Think about how can you solve the case with the tree with this.

$$$O(N + M * log(M))$$$ due to sort

// by paradox
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define y1 y1234567890
 
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file_io(s) freopen((s)".in", "r", stdin); freopen((s)".out", "w", stdout)
 
const int N = 1e5;
const int M = N + 7;
const double EPS = 1e-10;
 
const int MOD = 1e9 + 7;
const ll INF = 2e13;
 
int a[M];
vector<pair<int, pii>> edges;
 
int sz[M], p[M];
ll mx[M], sum[M];
 
int getParent(int v) {
    return p[v] = (p[v] == v ? v : getParent(p[v]));
}
 
void merge(int v, int u, int w) {
    v = getParent(v);
    u = getParent(u);
    if (v == u)
        return;
    if (sz[v] < sz[u])
        swap(v, u);
 
    ll fromV = -INF, fromU = -INF;
    if (sum[v] <= mx[u]) {
        fromV = min(mx[u], 1LL * w) - sum[v];
    }
    if (sum[u] <= mx[v]) {
        fromU = min(mx[v], 1LL * w) - sum[u];
    }
    mx[v] = max(fromV, fromU);
    sum[v] += sum[u];
 
    p[u] = v;
    sz[v] += sz[u];
}
 
void solve() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        p[i] = i;
        sz[i] = 1;
        mx[i] = INF;
        sum[i] = a[i];
    }
    for (int i = 1; i <= m; i++) {
        int v, u, w;
        scanf("%d %d %d", &v, &u, &w);
        edges.pb({w, {v, u}});
    }
    sort(all(edges));
    reverse(all(edges));
 
    for (auto &edge : edges) {
        merge(edge.se.fi, edge.se.se, edge.fi);
    }
 
    int v = getParent(1);
    if (sz[v] != n || mx[v] < 1) {
        printf("-1\n");
    } else {
        printf("%lld\n", mx[v]);
    }
}
 
int main() {
    int tt = 1;
    // scanf("%d", &tt);
    while (tt--) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma,tune=native")
#define vec vector
#define str(x) to_string(x)
#define len(x) int(x.size())
#define all(x) begin(x), end(x)
#define rep(x, from, to) for(int x = from; x < to; x++)
#define repd(x, from, to) for(int x = from - 1; x >= to; x--)
#define lbound(arr, x) distance(begin(arr), lower_bound(all(arr), x))
#define ubound(arr, x) distance(begin(arr), upper_bound(all(arr), x))
#ifndef ONLINE_JUDGE
#define dbg(x) cout << #x << " =\n" << x << "\n";
#else
#define dbg(x) 0
#endif
using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using uchar = unsigned char;
using pii = pair<int, int>;
using pill = pair<int, ll>;
using plli = pair<ll, int>;
using vi = vec<int>;
using vpii = vec<pii>;
using vplli = vec<plli>;
using vpill = vec<pill>;
using vll = vec<ll>;
using vull = vec<ull>;
using vchar = vec<char>;
using vuchar = vec<uchar>;
using vstr = vec<string>;
using vuint = vec<uint>;
using graph = vec<vi>;
using wgraph = vec<vpii>;

template<class A>
ostream& operator<<(ostream& o, const vector<A> a) {
    for(auto v: a)
        o << v << " ";

    return o << "\n";
}

template<class A>
ostream& operator<<(ostream& o, const set<A> a) {
    for(auto v: a)
        o << v << " ";
    
    return o << "\n";
}

template<class A>
ostream& operator<<(ostream &o, const multiset<A> a) {
    for(auto v: a)
        o << v << " ";
    
    return o << "\n";
}

template<class A, class K>
ostream& operator<<(ostream &o, const map<A, K> a) {
    for(auto [k, v]: a)
        o << k << ": " << v << "\n";

    return o;
}

template<class A, class B>
ostream& operator<<(ostream &o, const pair<A, B> p) {
    return o << p.first << " " << p.second << "\n";
}

vector<int> order;
vector<vector<int>> g;

void add(int u, int v) {
    g[u].push_back(v);        
}

int get_order(int u) {
    if(order[u] != -1) return order[u];
    if(g[u].empty()) return (order[u] = 0);
    order[u] = get_order(g[u].back());
    for(int i = len(g[u]) - 2; i >= 0; i--) order[u] = max(order[u], get_order(g[u][i]) + 1);
    return order[u];
}

void solve_testcase(int tc) {
    string s;
    cin >> s;
    int n = len(s), cnt = 0;
    order = vi(n, -1);
    g = vec<vi>(n);
    stack<int> st;
    st.push(0);
    for(int i = 0; i < n; i++) {
        if(s[i] == '(') st.push(++cnt);
        if(s[i] == ')') {
            int v = st.top();
            st.pop();
            add(st.top(), v);
        }
        if(s[i] == '-') i++;
    }
    cout << get_order(0) << "\n"; 
}

int main() {
    const bool MULTITEST = false, STRESS_TEST = false;
    #ifdef ONLINE_JUDGE
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    #else
        if(STRESS_TEST) {
            freopen("input.txt", "r", stdin);
            freopen("output.txt", "w", stdout);
        }
    #endif
    int tests;
    if(MULTITEST) cin >> tests;
    else tests = 1;
    rep(i, 0, tests) solve_testcase(i + 1);
    #ifndef ONLINE_JUDGE
        cout << "Press any key...";
        string s;
        cin >> s;
        exit(0);
    #endif
}

 

#include <bits/stdc++.h>
 
#define db double
#define ll long long
#define ld long double
#define ull unsigned long long
#define vint vector <int>
#define vpii vector <pii>
 
#define pii pair <int,int>
#define fi first
#define se second
#define pb emplace_back
#define mem(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
 
inline int read(){
	int x=0; char s=getchar();
	while(!isdigit(s))s=getchar();
	while(isdigit(s))x=x*10+s-'0',s=getchar();
	return x;
}
 
const ld eps=1e-6;
const ll N=2e5;
 
ld max(ld x,ld y){return x>y?x:y;}
ld min(ld x,ld y){return x<y?x:y;}
bool Eq(ld x,ld y){return fabs(x-y)<eps;}
bool Isz(ld x){return fabs(x)<eps;}
 
ld up,down,left,right;
ld dis(ld x1,ld y1,ld x2,ld y2){return sqrt((x1-x2)*(x1-x2)+((y1-y2)*(y1-y2)));}
ld dis(ld x1,ld y1,ld x2,ld y2,ld r){
	ld dot=x1*x2+y1*y2,d=dis(0,0,x2,y2);
	if(dot<eps)return max((ld)0,d-r);
	ld nd=dot/dis(0,0,x1,y1);
	return max((ld)0,sqrt(d*d-nd*nd)-r);
}
 
int swp,type;
void ref(int &x,int &y){int t=y; y=x,x=-t;} // counterclockwise rotate
ld query(int x,int y){
	for(int j=1;j<=swp;j++)ref(x,y);
	std::cout<<"? "<<x<<" "<<y<<std::endl;
	ld res; std::cin>>res; return res;
}
void answ(int x,int y,int r){
	for(int j=1;j<=swp;j++)ref(x,y);
	std::cout<<"! "<<x<<" "<<y<<" "<<r<<std::endl,exit(0);
}
void answer(ld x,ld y,ld r){
	int xx=x<0?x-eps:x+eps,yy=y<0?y-eps:y+eps;
	return answ(xx,yy,r+eps);
}
 
int main(){
	up=query(0,10),down=query(0,-10),left=query(-10,0),right=query(10,0);
	type=Isz(up)+Isz(down)+Isz(left)+Isz(right);
	if(type==0){
		ld mx=max(max(up,down),max(left,right));
		if(down==mx&&right==mx)swp=1;
		if(right==mx&&up==mx)swp=2;
		if(up==mx&&left==mx)swp=3;
	}
	if(type==1){if(Isz(left))swp=1; if(Isz(down))swp=2; if(Isz(right))swp=3;}
	if(type==2){
		if(Isz(left)&&Isz(up))swp=1;
		if(Isz(down)&&Isz(left))swp=2;
		if(Isz(right)&&Isz(down))swp=3;
	}
	up=query(0,10),down=query(0,-10),left=query(-10,0),right=query(10,0);
	
	int l=1,r=N*2-1,xx,yy,tx,ty; ld res;
	while(l<r){
		int m=l+r>>1;
		xx=-min(N,m),yy=N-max(0,m-N);
		(res=query(xx,yy))>1e-6?r=m:l=m+1;
	} xx=-min(N,l),yy=N-max(0,l-N);
	ld upl=query(tx,ty); ref(tx,ty),ref(tx,ty);
	ld downr=query(tx,ty),mdis=std::min(upl,downr);
	
	int xx2,yy2; l=1,r=N*3-1;
	while(l<r){
		int m=(l+r>>1)+1;
		xx2=min(N,m),yy2=-N+max(0ll,m-N);
		(res=query(xx2,yy2)>1e-6)?l=m:r=m-1;
	} xx2=min(N,l),yy2=-N+max(0,l-N),res=query(xx2,yy2);
	
	for(int r=1;r<=1e5;r++){
		ld y=mdis+r,x=sqrt((down+r)*(down+r)-y*y);
		ll d=1ll*xx*xx+1ll*yy+yy;
		ld sn=(ld)fabs(yy)/(ld)(sqrt(d)); // rotate the plane by some angle
		ld cs=(ld)fabs(xx)/(ld)(sqrt(d));
		if(Eq(mdis,upl))x=-x;
		ld x0=x*cs+y*sn,y0=-x*sn+y*cs; x=x0,y=y0;
		if(Eq(res,dis(xx2,yy2,x,y,r)))answer(x,y,r);
	}
	return 0;
}