萌新刚学倍增,80分求助/kk
查看原帖
萌新刚学倍增,80分求助/kk
363513
Lonely_Romance楼主2022/7/28 11:53

RT

// Problem: P1084 [NOIP2012 提高组] 疫情控制
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1084
// Memory Limit: 125 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,x,y,z) for(long long i=x;i<=y;i+=z)
#define fd(i,x,y,z) for(long long i=x;i>=y;i-=z)
ll n,m;
ll l,r;
ll tpp[50005];
ll fa[50005][19];
ll a[50005];
ll b[50005],vis[50005];
ll dep[50005],s[50005];
vector<ll> v[50005],u[50005],g;
struct Node{
	ll no,rm;
}t[50005];
bool cmp(Node x,Node y){
	return x.rm-s[x.no]>y.rm-s[y.no];
}
bool cpm(ll x,ll y){
	return x>y;
}
void dfs1(ll now,ll last,ll tp){
	if(tp==0&&now!=1){
		tp=now;
	}
	else if(v[last].size()>2){
		tp=now;
	}
	tpp[now]=tp;
	dep[now]=dep[last]+1;
	fa[now][0]=last;
	for(ll i=1;(1<<i)<=dep[now];i++){
		fa[now][i]=fa[fa[now][i-1]][i-1];
	}
	for(ll i=0;i<v[now].size();i++){
		ll yyy=v[now][i];
		if(yyy!=last){
			s[yyy]=s[now]+u[now][i];
			dfs1(yyy,now,tp);
		}
	}
}
void dfs2(ll now,ll last,ll tp){
	if(tp==0&&now!=1){
		tp=now;
	}
	
	if(v[now].size()==1){
		if(!vis[tp]){
			vis[tp]=1;
			g.push_back(s[tp]);
		}
	}
	for(ll i=0;i<v[now].size();i++){
		ll yyy=v[now][i];
		if(yyy!=last&&!b[yyy]){
			dfs2(yyy,now,tp);
		}
	}
}
bool check(ll x){
	memset(b,0,sizeof(b));
	memset(vis,0,sizeof(vis));
	g.clear();
	f(j,1,m,1){
		ll tot=x;
		ll now=a[j];
		fd(i,16,0,1){
			if((1<<i)>dep[now]){
				continue;
			}
			else{
				if(s[now]-s[fa[now][i]]<=tot&&fa[now][i]>1){
					tot-=s[now]-s[fa[now][i]];
					now=fa[now][i];
				}
			}
		}
		b[tpp[now]]++;
		t[j].no=now,t[j].rm=tot;
	}
	sort(t+1,t+m+1,cmp);
	dfs2(1,0,0);
	sort(g.begin(),g.end(),cpm);
	bool flag=true;
	for(ll i=0;i<g.size();i++){
		if(g[i]!=0){
			flag=false;
		}
	}
	if(flag){
		return true;
	}
	ll h=0;
	f(i,1,m,1){
		if(h>=g.size()){
			break;
		}
		if(b[tpp[t[i].no]]>1){
			//printf("%lld %lld %lld %lld 假\n",tpp[t[i].no],i,s[t[i].no]+g[h],t[i].rm);
			if(s[t[i].no]+g[h]>t[i].rm){
				return false;
			}
			else{
				b[tpp[t[i].no]]--;
				h++;
			}
		}
	}
	if(h<g.size()){
		return false;
	}
	else{
		return true;
	}
}
int main(){
	scanf("%lld",&n);
	f(i,1,n-1,1){
		ll xx,yy,zz;
		scanf("%lld%lld%lld",&xx,&yy,&zz);
		r+=zz;
		v[xx].push_back(yy);
		v[yy].push_back(xx);
		u[xx].push_back(zz);
		u[yy].push_back(zz);
	}
	scanf("%lld",&m);
	f(i,1,m,1){
		scanf("%lld",&a[i]);
	}
	dfs1(1,0,0);
	// f(i,1,n,1){
		// printf("%lld ",s[i]);
	// }
	// printf("\n");
	while(l<r){
		ll mid=(l+r)>>1;
		if(check(mid)){
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	printf("%lld\n",(l+r)>>1);
	return 0;
}
2022/7/28 11:53
加载中...