1 条题解
-
0
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
- 上传者