[acnoi2022] not a structure, more like a structure

subject

Title Description
to $n$ spot $m$ Edge undirected graph . Initially all edges are $\text{DDG}$ Guard and cannot pass . however , remember $S_i$ The connected block formed for the passable edges contains $i$ the , if ${\sum }_{x\in S_u}{a}_x+{\sum }_{y\in S_v}{a}_y⩾e_{a,b}$ And $v\notin S_u$, be $*u,v*$ The black bridge can be built on （ Would not have been $\text{DDG}$ The intrusion of ） And so it can be passed ！ Of course $S$ Will also change accordingly .

In all scenarios , Under the premise that the total number of black bridges built is the largest , The construction sequence with the smallest dictionary order .

Data range and tips
$n⩽10^5$, Border right $e_{u,v}⩽10^6$, Point right $a_i\in [0,10^6]$ .

Ideas

Save the flow ： There is no reference value . Just memorize it as a conclusion .

First reaction ： Maintenance required $\mathcal{O}(\mathrm{deg})$ Information about . Heuristic merging ？ Divide and conquer big and small points ？ Didn't get through .

An obscure condition ： The judgment condition of an edge is only related to the change of two values . So there was a way that could not be thought of by ordinary people like me ： For each edge , Suppose that $\text{sum}(S_u)+\text{sum}(S_v)$ still need sth. $\delta$ Increase of . be $\text{sum}(S_u)$ and $\text{sum}(S_v)$ At least one of them has $\lceil \frac{\delta }{2}\rceil$ Increase of .

So the $\mathrm{t}\mathrm{a}\mathrm{g}$ In the play , Check when triggered , Merging connected blocks is heuristic merging . One edge is only checked $\log e$ Time , Therefore, the total complexity is low $\mathcal{O}[m\log m(\log m+\log e)]$ or $\mathcal{O}(m\log m\log e)$ .

Code

#include <cstdio>
#include <algorithm> // Almighty XJX yyds!!
#include <cstring> // oracle: ZXY yydBUS!!!
#include <cctype> // Huge Egg Dog ate me!!!
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <utility>
#include <queue>
using namespace __gnu_pbds;
using llong = long long;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
# define rep0(i,a,b) for(int i=(a); i!=(b); ++i)
inline int readint(){
    
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar()) if(c == '-') f = -f;
	for(; isdigit(c); c=getchar()) a = a*10+(c^48);
	return a*f;
}

const int MAXN = 100000;
using PII = std::pair<int,int>;
tree<PII,null_type,std::less<PII>,splay_tree_tag> tre[MAXN];
int val[MAXN], fa[MAXN];
inline int findSet(int a){
    
	if(fa[a] == a) return a;
	return fa[a] = findSet(fa[a]);
}

std::priority_queue<int> todo;
int cost[MAXN<<1], ep[MAXN<<1][2];
std::queue<int> ans;
int main(){
    
	int n = readint(), m = readint();
	rep0(i,0,n) val[i] = readint(), fa[i] = i;
	for(int i=0,a,b; i!=m; ++i){
    
		a = ep[i][0] = readint()-1;
		b = ep[i][1] = readint()-1;
		cost[i] = readint();
		if(val[a]+val[b] >= cost[i]) todo.push(-i);
		else{
     // half to check
			tre[a].insert(PII{
    (cost[i]+1+val[a]-val[b])>>1, i});
			tre[b].insert(PII{
    (cost[i]+1-val[a]+val[b])>>1, i});
		}
	}
	while(!todo.empty()){
    
		int x = -todo.top(); todo.pop();
		if(findSet(ep[x][0]) == findSet(ep[x][1])) continue;
		int faa = findSet(ep[x][0]), fab = findSet(ep[x][1]);
		if(tre[fab].size() > tre[faa].size()) tre[faa].swap(tre[fab]);
		for(const PII &v : tre[fab]) tre[faa].insert(v);
		val[faa] += val[fab], ans.push(x), fa[fab] = faa;
		while(!tre[faa].empty() && tre[faa].begin()->first <= val[faa]){
    
			x = tre[faa].begin()->second;
			tre[faa].erase(tre[faa].begin());
			if(findSet(ep[x][0]) == findSet(ep[x][1])) continue;
			int l = findSet(ep[x][0]), r = findSet(ep[x][1]);
			if(val[l]+val[r] >= cost[x]) todo.push(-x); // available
			else{
     // still cut in half
				tre[l].insert(PII{
    (cost[x]+1+val[l]-val[r])>>1, x});
				tre[r].insert(PII{
    (cost[x]+1-val[l]+val[r])>>1, x});
			}
		}
	}
	printf("%d\n",int(ans.size()));
	for(; !ans.empty(); ans.pop())
		printf("%d ",ans.front()+1);
	putchar('\n');
	return 0;
}