当前位置:首页 » 其他

[攻城掠池]

2016-01-29 17:09 本站整理 浏览(11)

【问题描述】

从前有两个国家,为避免牵扯到现实,不妨称其为A 国和B 国。B 国是个富

强的大国,而A国是个衰落的小国。B 国对A 国虎视眈眈已久,终于在某一天,

对A国发起了侵略。

A国有n 个城市,某些城市之间有道路相连,道路可以双向通行。设第i 条

道路的长度为i l ,所有人——不管是A 国的市民还是B 国的侵略军——都需要花

费i l 个单位时间通过这条道路。任意两个A 国的城市之间有且只有一条互达的路

径,也就是说, A国的道路网络构成一棵树。

不妨把A国的城市编号为1 ~ n,并把A国的首都编号为1号。我们定义“边

界城市”为,以首都为根时,为叶子节点的城市。显然,这些城市会首当其冲地

受到侵略。

B 国也的确是这么打算的。作为侵略计划的第一步,B 国直接占领了A 国的

所有边界城市。我们从这个时刻开始计时,记这个时刻为时刻0 。B 国拥有特别

的训练技巧,可以把A 国每个被占领的城市当做自己侵略军的训练营。A 国每个

被占领的城市每个单位时间可以训练出一个士兵。假如某城市在时刻x 被占领,

这个城市在每个时刻x  i(i 1)都会训练出一个士兵。

B 国侵略计划的第二步是,从边界城市出发,不断把包围网向内缩进,直到

占领所有城市。因此,所有士兵都只会朝着首都的方向移动。当然,他们只能沿

着城市间的道路移动。

A国也不会束手就擒。在每个非边界城市中, A 国都有驻兵把守,城市i 中

有i d 个卫兵。当B 国的士兵进入一个有卫兵驻守的城市时,他会即时与一名卫兵

展开战斗,并瞬秒掉那名不幸的卫兵。换言之,我们可以认为一名士兵进入一个

城市时,卫兵数量就会减少1(如果还有卫兵的话)。而当一个城市中没有卫兵了

之后,这个城市就被B 国占领了,也就可以为B 国训练士兵了。

而B 国的士兵也比较奇怪,不会在同一个城市虐两个卫兵。也就是说设定是,

他在虐掉一名卫兵(或者发现这个城市没有卫兵)之后,就会继续朝着首都方向

赶路。而当他赶到了首都并虐了一名首都的卫兵(或者发现首都也没有卫兵)之

后,就要被强制回老家结婚了。

显然,一定存在某个时刻,使得A 国的所有城市恰好都被占领了。你的任务

就是求出这样的时刻。

【输入文件】

输入文件的第一行含有一个整数n ,含义如文中所述。

接下来一行含有n 个非负整数,第i 个整数为i d ,含义如文中所述。保证边

界城市满足 0 i d ,同时,保证所有非边界城市满足 0 i d 。

接下来n 1行,每行含有三个整数,描述一条道路。第i 行的三个整数为

i i i x , y , l ,代表编号为i x 和i y 的城市之间有一条长度为i l 的道路。保证道路网络构

成一棵树。

【输出文件】

输出一行一个整数,表示A 国的所有城市恰好都被占领的时刻。

【输入输出样例】

conquer.in conquer.out

5

5 10 0 0 0

1 2 3

1 3 10

2 4 1

2 5 2

7

6

50 40 30 20 10 0

1 2 1

2 3 2

3 4 3

4 5 4

5 6 5

38

【数据规模和约定】

对于10%的数据,满足n <=10。

对于40%的数据,满足n <=1000。

对于另20%的数据,保证树的形态为一条链。

对于100%的数据,满足1<= n <=100000

Splay的启发式合并= =挖坑等以后再写题解吧。。so累。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 500010
using namespace std;
typedef long long ll;
int n;
int a[maxn];
struct Edge{
	int to,next;
	ll dis;
}edge[maxn*2];
int h[maxn],cnt;
void add(int u,int v,int d){
	cnt++;
	edge[cnt].to = v;
	edge[cnt].next = h[u];
	edge[cnt].dis = d;
	h[u] = cnt;
}
const int Rt = 1;
int root[maxn];
int que[maxn];
struct Splay{
	int fa[maxn],c[maxn][2];
	ll key[maxn],sum[maxn];
	int size[maxn],sz;
	void pushup(int d){
		sum[d] = sum[c[d][0]] + sum[c[d][1]] + key[d];
		size[d] = size[c[d][0]] + size[c[d][1]] + 1;
	}
	void rotate(int p,int x){
		int mark = p == c[x][1],y = c[p][mark ^ 1];
		int z = fa[x];
		if(x == c[z][0])c[z][0] = p;
		if(x == c[z][1])c[z][1] = p;
		if(y != 0)fa[y] = x;
		fa[p] = z;c[p][mark ^ 1] = x;
		fa[x] = p;c[x][mark] = y;
		pushup(x);
	}
	void splay(int p,int &rt){
		while(fa[p]){
			int x = fa[p],y = fa[x];
			if(y == 0)rotate(p,x);
			else if(x == c[y][0] ^ p == c[x][0])
			    rotate(p,x),rotate(p,y);
			else rotate(x,y),rotate(p,x);
		}
		rt = p;
		pushup(p);
	}
	int newnode(){
		++sz;
        c[sz][0] = c[sz][1] = 0;
        fa[sz] = 0;
		return sz;
	}
	void insert(ll k,int y,int pos){
		int now = root[y],f = now,mark = 0;
		while(now){
			f = now;
			if(key[now] <= k)now = c[now][mark = 1];
			else now = c[now][mark = 0];
		}
		now = pos;
		fa[now] = f;
		if(f != 0)c[f][mark] = now;
		c[now][0] = c[now][1] = 0;
		key[now] = k;
		splay(now,root[y]);
	}
	ll upperbound(ll k,int y){
		int now = root[y],f = now;
		while(now){
			if(key[now] <= k){
				if(f == root[y] && key[f] <= key[now])
				    f = now;
				now = c[now][1];
			}
			else f = now,now = c[now][0];
		}
		splay(f,root[y]);
		return k * size[c[f][0]] - sum[c[f][0]];
	}
	void merge(int x,int y){
		if(size[root[x]] > size[root[y]])
		    swap(root[x],root[y]);
		int head = 0,tail = 1;
		que[head] = root[x];
		while(head != tail){
			int x = que[head ++];
			if(c[x][0])que[tail ++] = c[x][0];
			if(c[x][1])que[tail ++] = c[x][1];
			insert(key[x],y,x);
		}
	}
}T;

int fa[maxn];
ll dis[maxn],mx[maxn],t[maxn];
void dfs(int u){
	for(int i = h[u];i;i = edge[i].next){
		int v = edge[i].to;
		if(v == fa[u])continue;
		fa[v] = u;
		dis[v] = dis[u] + edge[i].dis;
		dfs(v);
		mx[u] = max(mx[v] + edge[i].dis,mx[u]);
	}
}

void dfs2(int u){
	T.insert(1LL<<60,u,T.newnode());
	for(int i = h[u];i;i = edge[i].next){
		int v = edge[i].to;
		if(v == fa[u])continue;
		dfs2(v);
		T.merge(v,u);
	}
	ll L = 0,R = mx[u] + a[u];
	while(L < R){
		ll mid = L + R >> 1;
		if(T.upperbound(mid + dis[u],u) >= a[u])
		    R = mid;
		else L = mid + 1;
	}
	t[u] = R;
	T.insert(R + dis[u],u,T.newnode());
}
int main(){
	freopen("conquer.in","r",stdin);
	freopen("conquer.out","w",stdout);

	scanf("%d",&n);
	for(int i = 1;i <= n;i ++)
	    scanf("%d",&a[i]);
	int u,v,d;
	for(int i = 1;i < n;i ++){
		scanf("%d%d%d",&u,&v,&d);
		add(u,v,d);
		add(v,u,d);
	}
	dfs(Rt);
	dfs2(Rt);
	ll ans=0;
	for(int i = 1;i <= n;i ++)
	    ans = max(ans,t[i]);
	printf("%lld\n",ans);
	return 0;
}