记录编号	222315	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	攻城掠池	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	2.779 s
提交时间	2016-01-30 17:05:08	内存使用	10.21 MiB

#define LL long long
#define MAXN 100010UL
#define L(x) ch[x][0]
#define R(x) ch[x][1]
#define Max(a,b)((a)>(b)?(a):(b))

#include<cstdio>
#include<cstdlib>

using namespace std;

int ch[MAXN][2],first[MAXN],fa[MAXN];
LL tans,Ans,cnt[MAXN],val[MAXN],sum[MAXN];
LL dis[MAXN],Lt,Rt,mid,MAXD,f[MAXN],siz[MAXN];
int n,node,root[MAXN],tot,Root,head,tail,q[MAXN];

struct Edge{
	int v,next;LL w;
}edge[MAXN<<1];

inline void Add(int u,int v,LL w)
{
	edge[++tot].v=v;
	edge[tot].w=w;
	edge[tot].next=first[u];
	first[u]=tot;
}

inline void PushUp(int x)
{
	if(x){
		siz[x]=siz[L(x)]+siz[R(x)]+1;
		sum[x]=sum[L(x)]+sum[R(x)]+val[x];
	}
}

inline void dfs(int rt,int father)
{
	for(int i=first[rt];i;i=edge[i].next)
	    if(edge[i].v!=father){
			dis[edge[i].v]=dis[rt]+edge[i].w;
			dfs(edge[i].v,rt);
	    }
}

inline void Rotate(int p,int d)
{
	int x=fa[p];
	fa[p]=fa[x];ch[fa[x]][R(fa[x])==x]=p;
    if(ch[p][d])fa[ch[p][d]]=x;
    ch[x][!d]=ch[p][d];
    ch[p][d]=x;fa[x]=p;
	PushUp(x);
}

inline void Splay(int p,int f)
{
	int x,y,d;
	while(fa[p]!=f){
		x=fa[p];y=fa[x];
		d=(R(x)==p);
		if(y==f)Rotate(p,!d);
		else{
			if(ch[y][d]==x)Rotate(x,!d),Rotate(p,!d);
			else Rotate(p,!d),Rotate(p,d);
		}
	}
	PushUp(p);
}

inline void Insert(int x,int y)
{
	int fy=x;
	while(x){
		fy=x;
		if(val[y]<=val[x])x=L(x);
		else x=R(x);
	}
	fa[y]=fy;
	if(fy)ch[fy][val[y]>val[fy]?1:0]=y;
	L(y)=R(y)=0;Splay(y,0);
}

inline void merge(int x,int y)
{
 	head=0;tail=0;
	q[tail]=y;int p;
	while(head<=tail){
		p=q[head++];
		if(L(p))q[++tail]=L(p);
		if(R(p))q[++tail]=R(p);
		Insert(x,p);x=p;
	}
}

inline void Search(int x,LL lson,LL suml,LL ncan)
{
	if((val[x]+1)*(siz[L(x)]+1+lson)-sum[L(x)]-suml-val[x]>=cnt[Root]){
	    f[Root]=val[x]+1-dis[Root];
		if(L(x))Search(L(x),lson,suml,ncan);
		else{
            Lt=ncan+1;Rt=f[Root]-1;
			while(Lt<=Rt){
				mid=(Lt+Rt)>>1;
				if((mid+dis[Root])*lson-suml>=cnt[Root])
				    f[Root]=mid,Rt=mid-1;
				else Lt=mid+1;
			}
		}
	}
	else{
		if(R(x))Search(R(x),lson+siz[L(x)]+1,suml+sum[L(x)]+val[x],val[x]-dis[Root]);
		else{
            Lt=val[x]+1-dis[Root];Rt=f[Root]-1;
			while(Lt<=Rt){
				mid=(Lt+Rt)>>1;
				if((mid+dis[Root])*(siz[L(x)]+1+lson)-suml-sum[L(x)]-val[x]>=cnt[Root])
				    f[Root]=mid,Rt=mid-1;
				else Lt=mid+1;
			}
		}
	}
}

inline void Solve(int rt)
{
	if(!cnt[rt]){
		root[rt]=++node;
		f[rt]=0;siz[node]=1LL;
		sum[node]=val[node]=dis[rt];
		return;
	}
	bool son=false;
	for(int i=first[rt];i;i=edge[i].next)
	    if(dis[edge[i].v]>dis[rt]){
			Solve(edge[i].v);
			if(!son)root[rt]=root[edge[i].v],son=true;
			else{
				if(siz[root[edge[i].v]]<siz[root[rt]])
					merge(root[rt],root[edge[i].v]);
				else merge(root[edge[i].v],root[rt]);
				Splay(root[rt],0);
			}
	    }
	f[rt]=MAXD;
	Root=rt;Search(root[rt],0,0,0);
	Ans=Max(Ans,f[rt]);
	node++;val[node]=f[rt]+dis[rt];
	Insert(root[rt],node);root[rt]=node;
}

int main()
{
    freopen("conquer.in","r",stdin);
	freopen("conquer.out","w",stdout);
	int __size__ = 30 << 20;
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	    scanf("%lld",&cnt[i]),MAXD+=cnt[i];
	int u,v;LL w;
	for(int i=1;i<n;i++){
		scanf("%d%d%lld",&u,&v,&w);
		MAXD+=w;Add(u,v,w);Add(v,u,w);
	}
	dfs(1,0);Solve(1);
	printf("%lld",Ans);
}