记录编号	424380	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]决战前的黎明	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	1.563 s
提交时间	2017-07-13 12:50:29	内存使用	11.76 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include <vector>
#define ll long long
using namespace std;//思考好如何处理<号而不是<=; 再好好看看题!; 
const int maxn=200010;
vector <int> g[maxn];
vector <int> w[maxn];
struct q{
	ll x,y,z;
	inline bool operator <(const q &b)const {
		if(y==b.y)return z<b.z;
		return y<b.y;
	}
};
q caozuo[maxn];
inline bool cmp(q a,q b){
	if(a.x==b.x&&a.y==b.y)return a.z<b.z;
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
int n;
ll deep[maxn];
inline void dfs(int u,int f,ll dep){
	deep[u]=dep;
	for(int i=0;i<g[u].size();i++){
		if(g[u][i]!=f)dfs(g[u][i],u,dep+w[u][i]);
	}
}
inline int lowbit(int x){return x&(-x);}
int shu[maxn];
inline void add(int p,int d){
	while(p<=n+10){
		shu[p]+=d;
		p+=lowbit(p);
	}
}
inline ll find(int p){
	ll an=0;
	while(p>0){
		an+=shu[p];
		p-=lowbit(p);
	}
	return an;
}
inline void clear(int p){ 
	while(p<=n+10){
		if(shu[p])
		{
			shu[p]=0;
		}
		else break;
		p+=lowbit(p);
	}
}
ll ans=0;
inline void cdq(int l,int r){
	if(l==r)return ;
	int m=(l+r)>>1;
	cdq(l,m);cdq(m+1,r);
	int p=l,q=m+1;
	sort(caozuo+l,caozuo+m+1);
	sort(caozuo+m+1,caozuo+r+1);
	while(q<=r){
		while(p<=m&&caozuo[p].y<=caozuo[q].y){//那么首先要满足i<j且i到根节点的距离不能超过j到根节点的距离  第一个<  第二个<= 第三个同样<=; 
			add(caozuo[p].z,1);
			p++;
		}
		ans+=find(caozuo[q].z-1);
		q++;
	}
	for(int i=l;i<=p;i++){
		clear(caozuo[i].z);
	}
/*	for(int i=l;i<=p;i++){     //这里莫名其妙错了,还是改成清空了. 
		add(caozuo[i].z,-1);
	}*/
}
int main(){
	freopen("ZZ.in","r",stdin);
	freopen("ZZ.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&caozuo[i].y);
	for(int i=1;i<n;i++){
		int x,y,v;
		scanf("%d%d%d",&x,&y,&v);
		g[x].push_back(y);
		w[x].push_back(v);
		g[y].push_back(x);
		w[y].push_back(v);
	}
	dfs(1,1,0);
	for(int i=1;i<=n;i++){
		caozuo[i].x=deep[i];
		caozuo[i].z=i+2;
	}
	sort(caozuo+1,caozuo+n+1,cmp);
	/*for(int i=1;i<=n;i++){
		cout<<i<<" "<<caozuo[i].x<<" "<<caozuo[i].y<<" "<<caozuo[i].z<<endl;
	} */
	cdq(1,n);
	printf("%lld\n",ans);
/*	for(int i=1;i<=5;i++){
		add(i,i);
	}
	cout<<find(5)-find(3-1)<<endl;*/
	return 0;
}