WA #5 #7 #9 #10 求调
查看原帖
WA #5 #7 #9 #10 求调
567942
Atlansert楼主2023/2/20 15:54
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+10;
int n,m,k,pos[N];
vector<int> e[N];
vector<ll> w[N];
int dep[N],f[N][17];
ll d[N][17];
bool leaf[N];
inline void dfs(int u){
	if(u!=1&&e[u].size()==1) leaf[u]=1;
	dep[u]=dep[f[u][0]]+1;
	for(int i=1;i<=16&&f[f[u][i-1]][i-1];i++){
		f[u][i]=f[f[u][i-1]][i-1];
		d[u][i]=d[u][i-1]+d[f[u][i-1]][i-1];
	}
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i],ww=w[u][i];
		if(v==f[u][0]) continue;
		f[v][0]=u;d[v][0]=ww;
		dfs(v);
	}
}
inline pair<int,ll> arr(int x,ll tim){
	for(int i=16;i>=0;i--){
		if(dep[f[x][i]]>1&&tim>=d[x][i]){
			tim-=d[x][i];
			x=f[x][i];
		}
	}
	return pair<int,ll>(x,tim);
}
priority_queue<ll,vector<ll>,greater<ll> > q1,q2;
bool sol,is[N];
inline void dfs1(int u){
	if(is[u]||sol) return;
	if(leaf[u]){
		sol=1;
		return;
	}
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i];
		if(v==f[u][0]) continue;
		dfs1(v);
	}
}
inline bool check(ll mid){
	while(!q1.empty()) q1.pop();
	while(!q2.empty()) q2.pop();
	for(int i=1;i<=m;i++){
		pair<int,ll> p=arr(pos[i],mid);
		int now=p.first;ll tim=p.second;
		if(dep[now]==2){
			if(tim>d[now][0]) q1.push(tim-d[now][0]);
			else is[now]=1;
		}
		else is[now]=1;
	}
	for(int i=0;i<e[1].size();i++){
		int v=e[1][i];
		sol=0;dfs1(v);
		if(sol) q2.push(d[v][0]);
	}
	while(!q2.empty()&&!q1.empty()){
		while(!q1.empty()&&!q2.empty()&&q1.top()>=q2.top()){
			q1.pop(),q2.pop();
		}
		while(!q1.empty()&&!q2.empty()&&q1.top()<q2.top()){
			q1.pop();
		}
	}
	return q2.empty();
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;ll ww;scanf("%d%d%lld",&u,&v,&ww);
		e[u].push_back(v),w[u].push_back(ww);
		e[v].push_back(u),w[v].push_back(ww); 
	}
	dfs(1);
	scanf("%d",&m);
	for(int i=1;i<=m;i++) scanf("%d",&pos[i]);
	ll l=1ll,r=(1ll<<31),ans=-1ll;
	while(l<=r){
		ll mid=l+r>>1ll;
		if(check(mid)) ans=mid,r=mid-1ll;
		else l=mid+1ll;
	}
	printf("%lld",ans);
	return 0;
}
2023/2/20 15:54
加载中...