记录编号	317493	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]决战前的黎明	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.557 s
提交时间	2016-10-08 08:35:03	内存使用	11.73 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=200010;
struct edge{int to,dis,prev;}e[maxn<<1];
struct A{
	int id,d,w;
	bool operator<(const A &a)const{
		if(d!=a.d)return d<a.d;
		return id<a.id;
	}
};
void addedge(int,int,int);
void dfs(int);
void CDQ(int,int);
void add(int,int);
int query(int);
int n,last[maxn],len=0,prt[maxn]={0},c[maxn],x,y,z;
A a[maxn],b[maxn];
long long ans=0ll;
int main(){
#define MINE
#ifdef MINE
	freopen("ZZ.in","r",stdin);
	freopen("ZZ.out","w",stdout);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].w);
		a[i].id=i;
	}
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&z);
		addedge(x,y,z);
		addedge(y,x,z);
	}
	dfs(1);
	CDQ(1,n);
	printf("%lld",ans);
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
void addedge(int x,int y,int z){
	e[++len].to=y;
	e[len].dis=z;
	e[len].prev=last[x];
	last[x]=len;
}
void dfs(int x){
	for(int i=last[x];i;i=e[i].prev)if(e[i].to!=prt[x]){
		prt[e[i].to]=x;
		a[e[i].to].d=a[x].d+e[i].dis;
		dfs(e[i].to);
	}
}
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(i<=mid&&j<=r){
		if(a[i]<a[j])b[k++]=a[i++];
		else b[k++]=a[j++];
	}
	while(i<=mid)b[k++]=a[i++];
	while(j<=r)b[k++]=a[j++];
	for(int i=l;i<=r;i++){
		a[i]=b[i];
		if(a[i].id<=mid)add(a[i].w,1);
		else ans+=query(a[i].w);
	}
	for(int i=l;i<=r;i++)if(a[i].id<=mid)add(a[i].w,-1);
}
void add(int x,int d){
	while(x<=n){
		c[x]+=d;
		x+=lowbit(x);
	}
}
int query(int x){
	int ans=0;
	while(x){
		ans+=c[x];
		x-=lowbit(x);
	}
	return ans;
}
/*
三维偏序裸题。
n个三元组(i,j,k)，求正序对数目。
对第一维(位置)分治，第二维(距离)排序，第三维(军队数)一发树状数组就好啦。
复杂度O(nlog^2n)。
话说明明同样是O(nlog^2n)的树套树为啥就过不了......
*/