90分求助
查看原帖
90分求助
180242
kradcigam楼主2020/8/5 12:23
#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T&x){
	x=0;T f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	x*=f;
}
const int MAXN=5e4+10;
int fa[30][MAXN],dist[MAXN],dep[MAXN],n,m,a[MAXN],b[MAXN],g[MAXN],T;
bool f[MAXN];
vector<pair<int,int> >v[MAXN];
set<int>k;
vector<int>d;
multiset<int>s;
void dfs(int x,int fa){
	dep[x]=dep[fa]+1;
	::fa[0][x]=fa;
	for(int i=1;i<=T;i++)::fa[i][x]=::fa[i-1][::fa[i-1][x]];
    bool flag=true;
	for(auto i:v[x])
		if(i.first!=fa){
            flag=false;
			dist[i.first]=dist[x]+i.second;
			dfs(i.first,x);
		}
    if(flag)d.push_back(x);
}
void dfs2(int x,int fa){
	for(auto i:v[x])
		if(i.first!=fa){
			f[i.first]|=f[x];
            dfs2(i.first,x);
		}
}
bool check(int x){
    s.clear();k.clear();
    memset(g,0x3f,sizeof(g));
    memset(f,false,sizeof(f));
    for(int i=1;i<=m;i++){
        if(dist[a[i]]<=x)s.insert(x-dist[a[i]]),g[b[a[i]]]=min(g[b[a[i]]],x-dist[a[i]]);
        else{
            int k=a[i];
            for(int j=T;j>=0;j--)
                if(dist[a[i]]-dist[fa[j][k]]<=x)k=fa[j][k];
            f[k]=true;
        }
    }
    dfs2(1,0);
    for(int i:d)
        if(!f[i])k.insert(b[i]);
    for(int i:k){
        auto a=lower_bound(s.begin(),s.end(),min(dist[i],g[i]));
        if(a==s.end())return false;
        s.erase(a);
    }return true;
}
int main(){
	read(n);T=16;
	for(int i=1;i<n;i++){
		int u,v,w;read(u);read(v);read(w);
		::v[u].push_back(make_pair(v,w));
		::v[v].push_back(make_pair(u,w));
    }dfs(1,0);
    read(m);
    for(int i=1;i<=m;i++)read(a[i]);
    for(int i=1;i<=n;i++){
        b[i]=i;
        for(int j=T;j>=0;j--)
            if(fa[j][b[i]]!=0&&fa[j][b[i]]!=1)b[i]=fa[j][b[i]];
    }
	int l=0,r=INT_MAX/2;
    while(l+1<r){
        int mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid;
    }
    if(r==INT_MAX/2)puts("-1");
    else cout<<r;
	return 0;
}

请求除了手写STL的其他方法

2020/8/5 12:23
加载中...