萌新刚学OI求助
查看原帖
萌新刚学OI求助
1052984
TimeLimitEnough楼主2023/7/31 16:34

调了一天了

#include<algorithm>
#include<iostream>
#include<vector>
#define mp make_pair
#define int long long 
using namespace std;
inline int read(){
	int x=0;char ch=getchar();
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
const int N=5e4+10;
vector<pair<int,int> > e[N];
int n,m,cnt;
int fa[N][21],dis[N][21],pre[N];
bool ok[N],need[N];
pair<int,int> gt[N];
void dfs1(int u,int father){//当前点是否合法 
	if(ok[u]) return;
	ok[u]=true;
	bool noson=true;
	for(pair<int,int> v:e[u]){
		if(v.second==father) continue;
		dfs1(v.second,u);
		ok[u]=ok[u] && ok[v.second];
		noson=false;
	}
	if(noson) ok[u]=false;
}
void dfs(int u,int father,int val){//倍增预处理 
	fa[u][0]=father,dis[u][0]=val;
	for(pair<int,int> v:e[u]) if(v.second!=father) dfs(v.second,u,v.first);
}
bool pd(int x){//check 函数 
	cnt=0;
	for(int i=1;i<=n;++i) ok[i]=false;
	for(int i=1;i<=m;++i) gt[i]=mp(0,0);
	for(int i=1;i<=m;++i){
		int tmp=pre[i],tm=x;
		for(int j=20;j>=0;--j) if(fa[tmp][j]>1 && dis[tmp][j]<tm) tm-=dis[tmp][j],tmp=fa[tmp][j];
		if(fa[tmp][0]==1 && tm>dis[tmp][0]) gt[++cnt]=mp(tm,tmp);//convenient army
		else ok[tmp]=true;//cities that are ready
	}
	dfs1(1,0);//DP on tree
	for(int i=1;i<=cnt;++i){
		int tmp=gt[i].first-dis[gt[i].second][0];
		if(!ok[gt[i].second] && gt[i].first<=dis[gt[i].second][0]*2) ok[gt[i].second]=true,gt[i]=mp(0,0);
		else gt[i]=mp(tmp,1);
	}
	sort(gt+1,gt+cnt+1);
	for(pair<int,int> v:e[1])
		if(!ok[v.second]){
			if(gt[cnt].first<v.first || cnt<=0) return false;
			cnt--;
		}
	return true;
}
bool cmp(pair<int,int> tmp_a,pair<int,int> tmp_b){
	return tmp_a>tmp_b;
}
signed main(){
	n=read();
	int tot=0;
	for(int i=1;i<n;++i){
		int u=read(),v=read(),val=read();
		e[u].push_back(mp(val,v));
		e[v].push_back(mp(val,u));
		tot+=val;
	}
	sort(e[1].begin(),e[1].end(),cmp);//贪心 
	dfs(1,0,0);
	for(int j=1;j<=20;++j) for(int i=1;i<=n;++i) fa[i][j]=fa[fa[i][j-1]][j-1],dis[i][j]=dis[i][j-1]+dis[fa[i][j-1]][j-1];
//	for(int i=1;i<=n;++i){
//		for(int j=0;j<=20;++j) cout<<dis[i][j]<<' ';cout<<'\n';
//	}
	m=read();
	for(int i=1;i<=m;++i) pre[i]=read();
	int l=0,r=tot+1;
	while(l<r){//dichotomy
		int mid=(l+r)>>1;
		if(pd(mid)) r=mid;
		else l=mid+1;
	}
	if(l==tot+1) cout<<"-1";
	else cout<<l;
	return 0;
}
2023/7/31 16:34
加载中...