AT_arc115_f

一个跑了整整 3900ms 的做法。

考虑如果当前有一个状态 $A$ 能在和不超过 $lim$ 的前提下到达一个状态 $B$，则 $B$ 在同样条件的前提下也能到达 $A$。

于是对于初始状态 $S$，会发现最优策略一定是先把和变得尽可能小，达到状态 $R$，以此让某些要经过很大值的点通过，然后再变成结束状态 $T$。

如果我们想知道一个状态 $A$ 在操作过程中和不超过 $lim$ 的前提下，和尽可能小的状态 $B$ 是简单的。考虑记录 $d_{i,j}$ 表示一个棋子从 $i$ 点移动到 $j$ 点，其他不动，会使和 $s$ 增加多少。

容易发现我们只会把棋子从 $h_i$ 大的移动到 $h_i$ 小的。同时，若 $dis_{i,j}<dis_{i,k}$，先移动到 $j$ 一定不劣。于是对于每个位置 $u$，下一次会移动到的点 $to_u$ 是固定的，只需要每次找可移动的点移动即可。一共会移动 $O(n^2)$ 次，使用优先队列优化后这一部分是 $O(n^2\log n)$ 的。

但是此时又发现一个问题：求 $R$ 是否能到达 $T$ 是困难的。但是由于一开始给出的结论，考虑对于 $T$ 求出它能到达的和最小的状态 $R'$，于是只用求 $R$ 是否能到达 $R'$。

这个判断是简单的，容易发现，若 $R$ 和 $R'$ 中两个对应的棋子的 $h$ 不同，则一定无解。因为若 $R$ 中的 $h_x$ 小于 $R'$ 中的 $h_y$，那么说明这个 $x$ 无法到达 $y$，否则 $R$ 会变化。于是只用判断此时 $R$ 的和 $sum$ 是否有 $sum+\max dis_{x,y}\le lim$ 即可。

同时这个 $lim$ 显然是可二分的，所以二分答案，复杂度为 $O(n^2\log V\log n)$。

然而此时大概率还无法通过。于是卡卡常，首先是发现设 $S,T$ 的和分别为 $s,t$，则二分边界可以设成 $l=\max(s,t),r=l+10^9$。同时，发现 at 的 c++17 比 c++20 要快。于是 3900ms 通过。

code：

int n,m,dis[N][N],a[N],b[N],c[N],f[N],g[N],to[N];
priority_queue<pii> q;
int tot,head[N];
struct node{
	int to,nxt;
}e[N<<1];
il void add(int u,int v){
	e[++tot]={v,head[u]},head[u]=tot;
}
void dfs(int u,int f,int s){
	go(i,u){
		int v=e[i].to;
		if(v==f){
			continue;
		}
		dis[s][v]=max(dis[s][u],c[v]-c[s]);
		dfs(v,u,s);
	}
}
bool check(ll lim){
	ll s=0,t=0;
	rep(i,1,m){
		s+=c[a[i]],t+=c[b[i]];
	}
	while(q.size()){
		q.pop();
	}
	rep(i,1,m){
		f[i]=a[i];
		if(to[f[i]]){
			q.emplace(-dis[f[i]][to[f[i]]],i);
		}
	}
	while(q.size()){
		int u=q.top().se,w=-q.top().fi;
		q.pop();
		if(s+w>lim){
			break;
		}
		s+=c[to[f[u]]]-c[f[u]];
		f[u]=to[f[u]];
		if(to[f[u]]){
			q.emplace(-dis[f[u]][to[f[u]]],u);
		}
	}
	while(q.size()){
		q.pop();
	}
	rep(i,1,m){
		g[i]=b[i];
		if(to[g[i]]){
			q.emplace(-dis[g[i]][to[g[i]]],i);
		}
	}
	while(q.size()){
		int u=q.top().se,w=-q.top().fi;
		q.pop();
		if(t+w>lim){
			break;
		}
		t+=c[to[g[u]]]-c[g[u]];
		g[u]=to[g[u]];
		if(to[g[u]]){
			q.emplace(-dis[g[u]][to[g[u]]],u);
		}
	}
	int mx=0;
	rep(i,1,m){
		if(c[f[i]]!=c[g[i]]){
			return 0;
		}
		mx=max(mx,dis[f[i]][g[i]]);
	}
	return s+mx<=lim;
}
void Yorushika(){
	read(n);
	rep(i,1,n){
		read(c[i]);
	}
	rep(i,1,n-1){
		int u,v;read(u,v);
		add(u,v),add(v,u);
	}
	rep(i,1,n){
		dfs(i,0,i);
	}
	rep(i,1,n){
		rep(j,1,n){
			if(c[j]<c[i]){
				if(!to[i]||dis[i][j]<dis[i][to[i]]){
					to[i]=j;
				}
			}
		}
	}
	read(m);
	ll s=0,t=0;
	rep(i,1,m){
		read(a[i],b[i]);
		s+=c[a[i]],t+=c[b[i]];
	}
	ll l=max(s,t),r=l+1e9,ans=1ll*inf*inf;
	while(l<=r){
		ll mid=(l+r)>>1;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	printf("%lld\n",ans);
}
signed main(){
	int t=1;
	// read(t);
	while(t--){
		Yorushika();
	}
}

话说好像不用二分，就不卡常了。