1 条题解

  • 0
    @ 2021-6-15 10:09:20

    C++ :

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<climits>
    #include<vector>
    #include<queue>
    #define fir first
    #define sec second
    using namespace std;
    const int N=50010;
    typedef pair<int,int> pii;
    vector<pii>G[N];
    typedef vector<pii>::iterator IT;
    
    int n,m,fa[N],anc[N],pos[N],g[N];
    bool cover[N];
    
    void build(int u,int color) {
    	if(fa[u]==1)color=u;
    	anc[u]=color;
    	for(IT it=G[u].begin();it!=G[u].end();it++) {
    		int v=it->fir,w=it->sec;
    		if(v==fa[u])continue;
    		fa[v]=u;
    		g[v]=w;
    		build(v,color);
    	}
    }
    
    int P[N][20],k;
    int L[N][20];
    pii city[N],egg[N];
    
    void init_table() {
    	while((1<<(k+1))<n)k++;
    	memset(P,-1,sizeof(P));
    	for(int i=1;i<=n;i++)P[i][0]=fa[i],L[i][0]=g[i];
    	for(int j=1;j<=k;j++)
    		for(int i=1;i<=n;i++)
    			if(P[i][j-1]!=-1&&P[P[i][j-1]][j-1]!=-1) {
    				P[i][j]=P[P[i][j-1]][j-1];
    				L[i][j]=L[i][j-1]+L[P[i][j-1]][j-1];
    			}
    }
    
    pii go(int s,int x) {
    	for(int j=k;j>=0;j--)
    		if(P[s][j]!=-1&&L[s][j]<=x) {
    			x-=L[s][j];
    			s=P[s][j];
    		}
    	return make_pair(s,x);
    }
    
    void DP(int u) {
    	if(cover[u])return;
    	bool isleaf=true;
    	for(IT it=G[u].begin();it!=G[u].end();it++) {
    		int v=it->fir;
    		if(v==fa[u])continue;
    		isleaf=false;
    		DP(v);
    		if(!cover[v]&&u!=1)return;
    	}
    	if(!isleaf)cover[u]=true;
    }
    
    bool cmpii(pii a,pii b) {
    	return a.sec<b.sec;
    }
    
    bool check(int M) {
    	memset(cover,0,sizeof(cover));
    	memset(city,0,sizeof(city));
    	memset(egg,0,sizeof(egg));
    	for(int i=1;i<=m;i++) {
    		pii u=go(pos[i],M);
    		int s=u.fir;
    		int x=u.sec;
    		if(s==1)egg[++egg[0].fir]=make_pair(pos[i],x);
    		else cover[s]=true;
    	}
    	DP(1);
    	for(IT it=G[1].begin();it!=G[1].end();it++) {
    		int v=it->fir;
    		if(!cover[v])city[++city[0].fir]=*it;
    	}
    	if(city[0].fir>egg[0].fir)return 0;
    	sort(city+1,city+city[0].fir+1,cmpii);
    	sort(egg+1,egg+egg[0].fir+1,cmpii);
    	int i,j;
    	i=j=1;
    	while(j<=city[0].fir) {
    		int c=city[j].fir;
    		int ct=city[j].sec;
    		if(cover[c]) {
    			j++;
    			continue;
    		}
    		if(i==egg[0].fir+1)break;
    		int e=egg[i].fir;
    		int et=egg[i].sec;
    		if(!cover[anc[e]]) {
    			cover[anc[e]]=true;
    			i++;
    		} else if(ct<=et) {
    			cover[c]=true;
    			i++;
    			j++;
    		} else i++;
    	}
    	return j==city[0].fir+1;
    }
    
    void init() {
    	scanf("%d",&n);
    	int u,v,w;
    	for(int i=1;i<n;i++) {
    		scanf("%d%d%d",&u,&v,&w);
    		G[u].push_back(make_pair(v,w));
    		G[v].push_back(make_pair(u,w));
    	}
    	fa[1]=-1;
    	build(1,0);
    	scanf("%d",&m);
    	for(int i=1;i<=m;i++)
    		scanf("%d",&pos[i]);
    	init_table();
    }
    
    int work() {
    	if(G[1].size()>m)return -1;
    	int l=0,r=INT_MAX,M;
    	while(l<r) {
    		M=(l+r)>>1;
    		if(check(M))r=M;
    		else l=M+1;
    	}
    	return r;
    }
    
    int main() {
    	init();
    	printf("%d\n",work());
    	return 0;
    }
    
    • 1

    信息

    ID
    310
    时间
    2000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者