记录编号	586618	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]决战前的黎明	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.346 s
提交时间	2024-02-18 23:28:03	内存使用	16.43 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+10;
int n;
struct made{
	int a,d;
}a[N],b[N];
struct node{
	int ver,nx,ed;
}e[N<<2];
int hd[N],tot;
void add(int x,int y,int z){
	tot++;
	e[tot].nx = hd[x],e[tot].ver = y,e[tot].ed = z,hd[x] = tot;
}
struct BIT{
	int c[N];
	inline int lowbit(int x){return x & (-x);}
	void add(int x,int val){
		for(;x <= n;x += lowbit(x))c[x] += val;
	}
	ll ask(int x){
		ll ans = 0;
		for(;x > 0;x -= lowbit(x))ans += c[x];
		return ans;
	}
}t;
ll ans;
void CDQ(int l,int r){
	if(l == r)return;
	int mid = l + r >> 1;
	CDQ(l,mid),CDQ(mid+1,r);
	int i = l,j = mid+1,k = l;
	while(j <= r){
		while(i <= mid && a[i].d <= a[j].d)t.add(a[i].a,1),b[k++] = a[i++];
		ans += t.ask(a[j].a),b[k++] = a[j++];
	}
	for(int u = l;u < i;u++)t.add(a[u].a,-1);
	while(i <= mid)b[k++] = a[i++];
	for(int i = l;i <= r;i++)a[i] = b[i];
}
void dfs(int x,int fa){
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(y == fa)continue;
		a[y].d = a[x].d + e[i].ed;
		dfs(y,x);
	}
}
int main(){
	freopen("ZZ.in","r",stdin);
	freopen("ZZ.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)scanf("%d",&a[i].a);
	for(int i = 1;i < n;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z),add(y,x,z);
	}
	dfs(1,0);
	CDQ(1,n);
	printf("%lld\n",ans);

	return 0;
	
}