自动搬运

查看原文

来自洛谷，原作者为

	dadaaa 加油

搬运于2025-08-24 23:05:35，当前版本为作者最后更新于2024-10-28 14:53:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先考虑 $V1\le V2$ 的情况，注意到，只要小偷不送死，警察只能够追到叶子在抓他。如果我们设 $P$ 为根，设 $d_x$ 为 $x$ 点到子树内深度最深点的距离，发现答案是 $P$ 到 $T$ 路径上所有不被抓到的点中 $\frac{d_i+a1_i}{V1}$ 最大的（表示警察所需要的时间）（$a1_i$ 表示 $i$ 到 $P$ 的距离，$a2_i$ 表示 $i$ 到 $T$ 的距离）。再考虑这个值在链上是单调的，越靠近 $P$ 的一定更大（反正警察追不到，越往上小偷选择越多）。因此答案就是链上最靠近 $P$ 的不被抓到的点的这个值，树剖完二分即可。对于每次询问，单点求 $d_i$ 是容易的（换根求最大次大）。

现在再考虑 $V1\gt V2$ 的情况。此时警察可能抓到小偷了，因此当我们小偷能走到链上的点 $i$ 时，警察抓到他所需要的时间是 $\min(\frac{a1_i+d_i}{V1},\frac{a1_i-a2_i}{V1-V2})$。（所有定义和前文相同）。注意到后面那项同样在链上单调（离警察越远越难追），所以我们树剖二分出分界点，最优值一定在分界点前后。为啥不用判断会不会在链上追到，会出负数？因为这样一定不优。

总复杂度 $O(n\log n)$。我写了5k，好像双 log 更好写

#include "police.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
const int N=1e5+10;
int n,q;
vector<pair<int,ll> > e[N];
ll mx[N],se[N],disrt[N];
int mxp[N],sep[N];
int sum[N],dep[N],Fa[N];
int son[N],top[N],in[N],p[N],timer;
void dfs1(int x,int fa) {
	sum[x]=1;
	Fa[x]=fa;
	dep[x]=dep[fa]+1;
	for(auto v:e[x]) if (v.first!=fa) {
		dfs1(v.first,x);
		sum[x]+=sum[v.first];
		if (sum[v.first]>sum[son[x]]) son[x]=v.first;
	}
}
void dfs2(int x,int cap) {
	top[x]=cap;
	p[in[x]=++timer]=x;
	if(son[x]) dfs2(son[x],cap);
	for(auto v:e[x]) if(v.first!=son[x]&&v.first!=Fa[x]) {
		dfs2(v.first,v.first);
	}
}
void upd(int x,ll d,int c) {
	if(d>mx[x]) {
		se[x]=mx[x],sep[x]=mxp[x];
		mx[x]=d,mxp[x]=c;
	} else if(d>se[x]) {
		se[x]=d,sep[x]=c;
	}
}
void dfs3(int x) {
	for(auto v:e[x]) if(v.first!=Fa[x]) {
		disrt[v.first]=disrt[x]+v.second;
		dfs3(v.first);
		upd(x,mx[v.first]+v.second,v.first);
	}
}
void dfs4(int x,ll d) {
	upd(x,d,Fa[x]);
	for(auto v:e[x]) if(v.first!=Fa[x]) {
		dfs4(v.first,max(d,mxp[x]!=v.first? mx[x]:se[x])+v.second);
	}
}
bool check(int x,int b,ll a1,ll a2,ll v1,ll v2) {
	ll di=(mxp[x]==b? se[x]:mx[x]);
	// cerr<<di<<'\n';
	return (1.0*di+1.0*a1)/(1.0*v1)<(1.0*a1-1.0*a2)/(1.0*v1-1.0*v2);
}
array<ll,2> query(int P,int T,ll v1,ll v2) {
	vector<pair<int,int> > up,dn;
	ll d=0,g,u=P,v=T;
	while(top[u]!=top[v]) {
		if(dep[top[u]]>dep[top[v]]) {
			up.emplace_back(in[u],in[top[u]]);
			u=Fa[top[u]];
		} else {
			dn.emplace_back(in[top[v]],in[v]);
			v=Fa[top[v]];
		}
	}
	if(dep[u]<dep[v]) g=u,dn.emplace_back(in[u],in[v]);
	else g=v,up.emplace_back(in[u],in[v]);
	d=disrt[P]+disrt[T]-disrt[g]*2;
	reverse(dn.begin(),dn.end());
	if(v1<=v2) {
		int lst=P;
		for(auto li:up) {
			int x=p[li.second],b=(li.second==li.first? lst:p[li.second+1]);
			ll a1=disrt[P]-disrt[x],a2=d-a1;
			if((1.0*a1)/(1.0*v1)<=(1.0*a2)/(1.0*v2)) {
				lst=x;
				continue;
			} 
			int l=li.first,r=li.second,res=li.second;
			while(l>=r) {
				int mid=(l+r+1)/2;
				int x=p[mid];//,b=(mid==li.first?lst:p[mid+1]);
				ll a1=disrt[P]-disrt[x],a2=d-a1;
				if((1.0*a1)/(1.0*v1)>(1.0*a2)/(1.0*v2)) res=mid,r=mid+1;
				else l=mid-1;
			}
			x=p[res],b=(res==li.first?lst:p[res+1]);
			a1=disrt[P]-disrt[x],a2=d-a1;
			ll di=(mxp[x]==b?se[x]:mx[x]);
			return {a1+di,v1};
		}
		for(auto li:dn) {
			int x=p[li.second],b=(li.second==li.first? lst:p[li.second-1]);
			ll a2=disrt[T]-disrt[x],a1=d-a2;
			if((1.0*a1)/(1.0*v1)<=(1.0*a2)/(1.0*v2)) {
				lst=x;
				continue;
			} 
			int l=li.first,r=li.second,res=li.second;
			while(l<=r) {
				int mid=(l+r)/2;
				int x=p[mid];//,b=(mid==li.first?lst:p[mid-1]);
				ll a2=disrt[T]-disrt[x],a1=d-a2;
				if((1.0*a1)/(1.0*v1)>(1.0*a2)/(1.0*v2)) res=mid,r=mid-1;
				else l=mid+1;
			}
			x=p[res],b=(res==li.first?lst:p[res-1]);
			a2=disrt[T]-disrt[x],a1=d-a2;
			ll di=(mxp[x]==b?se[x]:mx[x]);
			return {a1+di,v1};
		}
	} else {
		int lst=P;
		ll al1=0,al2=0;
		for(auto li:up) {
			int x=p[li.second],b=(li.first==li.second? lst:p[li.second+1]);
			ll a1=disrt[P]-disrt[x],a2=d-a1;
			if(!check(x,b,a1,a2,v1,v2)) {
				lst=x,al1=a1,al2=a2;
				continue;
			}
			int l=li.first,r=li.second,res=li.second;
			while(l>=r) {
				int mid=(l+r+1)/2;
				int x=p[mid],b=(mid==li.first?lst:p[mid+1]);
				ll a1=disrt[P]-disrt[x],a2=d-a1;
				if(check(x,b,a1,a2,v1,v2)) res=mid,r=mid+1;
				else l=mid-1;
			}
			x=p[res],b=(res==li.first?lst:p[res+1]);
			if(b!=lst) {
				al1=disrt[P]-disrt[b],al2=d-al1;
			}
			a1=disrt[P]-disrt[x],a2=d-a1;
			ll di=(mxp[x]==b?se[x]:mx[x]);
			db res1=(1.0*di+1.0*a1)/(1.0*v1),res2=(1.0*al1-1.0*al2)/(1.0*v1-1.0*v2);
			// cerr<<p[li.first]<<' '<<p[li.second]<<'\n';
			// cerr<<x<<' '<<res1<<' '<<res2<<'\n';
			if(res1>res2) return {di+a1,v1};
			else return {al1-al2,v1-v2};
		}
		for(auto li:dn) {
			int x=p[li.second],b=(li.first==li.second? lst:p[li.second-1]);
			ll a2=disrt[T]-disrt[x],a1=d-a2;
			if(!check(x,b,a1,a2,v1,v2)) {
				lst=x,al1=a1,al2=a2;
				continue;
			}
			int l=li.first,r=li.second,res=li.second;
			while(l<=r) {
				int mid=(l+r)/2;
				int x=p[mid],b=(mid==li.first?lst:p[mid-1]);
				ll a2=disrt[T]-disrt[x],a1=d-a2;
				if(check(x,b,a1,a2,v1,v2)) res=mid,r=mid-1;
				else l=mid+1;
			}
			x=p[res],b=(res==li.first?lst:p[res-1]);
			if(b!=lst) {
				al2=disrt[T]-disrt[b],al1=d-al2;
			}
			a2=disrt[T]-disrt[x],a1=d-a2;
			ll di=(mxp[x]==b?se[x]:mx[x]);
			db res1=(1.0*di+1.0*a1)/(1.0*v1),res2=(1.0*al1-1.0*al2)/(1.0*v1-1.0*v2);
			// cerr<<p[li.first]<<' '<<p[li.second]<<'\n';
			// cerr<<x<<' '<<res1<<' '<<res2<<'\n';
			if(res1>res2) return {di+a1,v1};
			else return {al1-al2,v1-v2};
		}
		return {d,v1-v2};
	}
	return {-1,-1};
} 

std::vector<std::array<long long, 2>> police_thief(std::vector<int> A, std::vector<int> B, std::vector<int> D,
	 std::vector<int> P, std::vector<int> V1, std::vector<int> T, std::vector<int> V2){
	n=A.size()+1,q=(int)P.size();
	for(int i=0;i<n-1;i++) {
		e[A[i]+1].emplace_back(B[i]+1,D[i]);
		e[B[i]+1].emplace_back(A[i]+1,D[i]);
	}
	dfs1(1,0);
	dfs2(1,1);
	dfs3(1);
	dfs4(1,0);
	// for(int i=1;i<=n;i++) cerr<<in[i]<<' ';
	// cerr<<'\n';
	std::vector<std::array<long long, 2>> C(q);
	for(int te=0;te<q;te++) {
		// cerr<<"TE\n";
		C[te]=query(P[te]+1,T[te]+1,V1[te],V2[te]);
	}
	// cerr<<mx[8]<<"\n";
	return C;
}