WA#6求调
查看原帖
WA#6求调
567942
Atlansert楼主2024/9/2 18:14
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+10;
int n,m,a[N];
int tot,head[N];
struct Edge{
	int to,nxt,w;
}edge[N<<1];
inline void Add(int from,int to,int w){
	edge[++tot].to=to;
	edge[tot].w=w;
	edge[tot].nxt=head[from];
	head[from]=tot;
} 
int dep[N],f[N][18],ff[N];
inline bool cmp(int a,int b){
	return dep[a]>dep[b];
}
ll t[N][18];
inline void dfs(int u){
	dep[u]=dep[f[u][0]]+1;
	if(dep[u]>2) ff[u]=ff[f[u][0]];
	for(int i=1;i<=17&&f[f[u][i-1]][i-1];i++){
		f[u][i]=f[f[u][i-1]][i-1];
		t[u][i]=t[u][i-1]+t[f[u][i-1]][i-1];
	}
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==f[u][0]) continue;
		f[v][0]=u;
		t[v][0]=1ll*edge[i].w;
		dfs(v);
	}
}
inline ll dis(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	ll ret=0ll;
	for(int i=17;i>=0;i--){
		if(dep[f[x][i]]>=dep[y]){
			ret+=t[x][i];
			x=f[x][i];
		}
	}
	if(x==y) return ret;
	for(int i=17;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			ret+=t[x][i]+t[y][i];
			x=f[x][i],y=f[y][i];
		}
	}
	return ret;
} 
bool is[N],leaf[N],sol;
inline void judge(int u){
	if(sol||is[u]) return;
	if(leaf[u]){
		sol=1;
		return;
	}
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==f[u][0]) continue;
		judge(v);
	}
}
inline int arr(int u,ll ret){
	for(int i=17;i>=0;i--){
		if(!f[u][i]||ret<t[u][i]) continue;
		ret-=t[u][i];
		u=f[u][i];
	}
	return u;
}
priority_queue<ll,vector<ll>,greater<ll> > q1,q2;
inline bool check(ll mid){
	while(!q1.empty()) q1.pop();
	while(!q2.empty()) q2.pop();
	memset(is,0,sizeof(is));
	for(int i=1;i<=m;i++){
		ll d=dis(1,a[i]);
		if(d<=mid){
			if(d+t[ff[a[i]]][0]<=mid){
				q1.push(mid-d);
	//			if(mid==12) printf("    %lld\n",mid-d);
			}
			else{
				sol=0;
				judge(ff[a[i]]);
				if(sol){
					is[ff[a[i]]]=1;
				}
				else{
					q1.push(mid-d);
	//				if(mid==12) printf("    %lld\n",mid-d);
					
				}
				
			}
		}
		else is[arr(a[i],mid)]=1;
	}
//	if(mid==12) printf("%d\n",q1.size());
	for(int i=head[1];i;i=edge[i].nxt){
		int v=edge[i].to;
		sol=0;
		judge(v);
		if(sol){
			q2.push(edge[i].w);
		}
	}
	while(q1.empty()==0&&q2.empty()==0){
		if(q2.top()<=q1.top()) q1.pop(),q2.pop();
		else q1.pop();
	}
	return q2.empty();
}
/*
10
2 1 3
2 3 4
1 4 7
5 1 9
6 1 2
4 7 9
7 8 8
9 8 8
1 10 2
5
2 8 5 4 2 

9
*/
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		Add(u,v,w),Add(v,u,w);
	}
	for(int i=head[1];i;i=edge[i].nxt) ff[edge[i].to]=edge[i].to;
	for(int i=1;i<=n;i++) if(!edge[head[i]].nxt) leaf[i]=1;
	dfs(1);
	scanf("%d",&m);
	for(int i=1;i<=m;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+m,cmp);
//	for(int i=1;i<=m;i++) printf("%d ",a[i]);printf("\n");
	ll l=1ll,r=1ll<<60,ans=-1;
	while(l<=r){
//		printf("%lld %lld\n",l,r);
		ll mid=l+r>>1;
		if(check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%lld",ans);
	return 0;
} #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+10;
int n,m,a[N];
int tot,head[N];
struct Edge{
	int to,nxt,w;
}edge[N<<1];
inline void Add(int from,int to,int w){
	edge[++tot].to=to;
	edge[tot].w=w;
	edge[tot].nxt=head[from];
	head[from]=tot;
} 
int dep[N],f[N][18],ff[N];
inline bool cmp(int a,int b){
	return dep[a]>dep[b];
}
ll t[N][18];
inline void dfs(int u){
	dep[u]=dep[f[u][0]]+1;
	if(dep[u]>2) ff[u]=ff[f[u][0]];
	for(int i=1;i<=17&&f[f[u][i-1]][i-1];i++){
		f[u][i]=f[f[u][i-1]][i-1];
		t[u][i]=t[u][i-1]+t[f[u][i-1]][i-1];
	}
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==f[u][0]) continue;
		f[v][0]=u;
		t[v][0]=1ll*edge[i].w;
		dfs(v);
	}
}
inline ll dis(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	ll ret=0ll;
	for(int i=17;i>=0;i--){
		if(dep[f[x][i]]>=dep[y]){
			ret+=t[x][i];
			x=f[x][i];
		}
	}
	if(x==y) return ret;
	for(int i=17;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			ret+=t[x][i]+t[y][i];
			x=f[x][i],y=f[y][i];
		}
	}
	return ret;
} 
bool is[N],leaf[N],sol;
inline void judge(int u){
	if(sol||is[u]) return;
	if(leaf[u]){
		sol=1;
		return;
	}
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==f[u][0]) continue;
		judge(v);
	}
}
inline int arr(int u,ll ret){
	for(int i=17;i>=0;i--){
		if(!f[u][i]||ret<t[u][i]) continue;
		ret-=t[u][i];
		u=f[u][i];
	}
	return u;
}
priority_queue<ll,vector<ll>,greater<ll> > q1,q2;
inline bool check(ll mid){
	while(!q1.empty()) q1.pop();
	while(!q2.empty()) q2.pop();
	memset(is,0,sizeof(is));
	for(int i=1;i<=m;i++){
		ll d=dis(1,a[i]);
		if(d<=mid){
			if(d+t[ff[a[i]]][0]<=mid){
				q1.push(mid-d);
	//			if(mid==12) printf("    %lld\n",mid-d);
			}
			else{
				sol=0;
				judge(ff[a[i]]);
				if(sol){
					is[ff[a[i]]]=1;
				}
				else{
					q1.push(mid-d);
	//				if(mid==12) printf("    %lld\n",mid-d);
					
				}
				
			}
		}
		else is[arr(a[i],mid)]=1;
	}
//	if(mid==12) printf("%d\n",q1.size());
	for(int i=head[1];i;i=edge[i].nxt){
		int v=edge[i].to;
		sol=0;
		judge(v);
		if(sol){
			q2.push(edge[i].w);
		}
	}
	while(q1.empty()==0&&q2.empty()==0){
		if(q2.top()<=q1.top()) q1.pop(),q2.pop();
		else q1.pop();
	}
	return q2.empty();
}
/*
10
2 1 3
2 3 4
1 4 7
5 1 9
6 1 2
4 7 9
7 8 8
9 8 8
1 10 2
5
2 8 5 4 2 

9
*/
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		Add(u,v,w),Add(v,u,w);
	}
	for(int i=head[1];i;i=edge[i].nxt) ff[edge[i].to]=edge[i].to;
	for(int i=1;i<=n;i++) if(!edge[head[i]].nxt) leaf[i]=1;
	dfs(1);
	scanf("%d",&m);
	for(int i=1;i<=m;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+m,cmp);
//	for(int i=1;i<=m;i++) printf("%d ",a[i]);printf("\n");
	ll l=1ll,r=1ll<<60,ans=-1;
	while(l<=r){
//		printf("%lld %lld\n",l,r);
		ll mid=l+r>>1;
		if(check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%lld",ans);
	return 0;
} 
2024/9/2 18:14
加载中...