记录编号 | 441996 | 评测结果 | AAAAAAAAAAAAAAAAAAAT | ||
---|---|---|---|---|---|
题目名称 | [NOIP 2015]运输计划 | 最终得分 | 95 | ||
用户昵称 | 是否通过 | 未通过 | |||
代码语言 | C++ | 运行时间 | 2.225 s | ||
提交时间 | 2017-08-26 07:43:05 | 内存使用 | 47.23 MiB | ||
#include<bits/stdc++.h> using namespace std; int n,m,head[300005],h,dep[300005],dis[300005],lc[300005][25],t,a[300005],f[600005]; struct edge{ int to,next,cost; }e[600005]; struct d{ int from,to,cost,lc; }q[300005]; void edge_add(int x,int y,int z){ e[++h].to=y; e[h].cost=z; e[h].next=head[x]; head[x]=h; e[++h].to=x; e[h].cost=z; e[h].next=head[y]; head[y]=h; } void dfs(int x){ for(int i=head[x];i;i=e[i].next){ if(!dep[e[i].to]){ dep[e[i].to]=dep[x]+1; dis[e[i].to]=dis[x]+e[i].cost; lc[e[i].to][0]=x; dfs(e[i].to); } } } void init_lca(){ dep[1]=1; dfs(1); for(int i=1;(1<<i)<=n;i++){ for(int j=1;j<=n;j++){ lc[j][i]=lc[lc[j][i-1]][i-1]; } } } int q_lc(int x,int y){ if(dep[x]<dep[y]){ swap(x,y); } int o=dep[x]-dep[y]; for(int i=0;i<=24;i++){ if(o&(1<<i)){ x=lc[x][i]; o-=(1<<i); } } for(int i=24;i>=0;i--){ if(lc[x][i]!=lc[y][i]){ x=lc[x][i]; y=lc[y][i]; } } if(x==y){ return x; } else{ return lc[x][0]; } } void dfs2(int x){ for(int i=head[x];i;i=e[i].next){ if(dep[e[i].to]<dep[x])continue; dfs2(e[i].to); a[x]+=a[e[i].to]; f[i]=a[e[i].to]; } } bool check(int x){ memset(a,0,sizeof(a)); memset(f,0,sizeof(f)); int ans=0,maa=-1;; for(int i=1;i<=t;i++){ if(q[i].cost>x){ a[q[i].from]++; a[q[i].to]++; a[q[i].lc]-=2; ans++; maa=max(maa,q[i].cost); } } if(maa==-1){ return 0; } /* for(int i=1;i<=6;i++) cout<<a[i]<<" "; */ dfs2(1); int ma=-1; for(int i=1;i<2*n;i++){ if(f[i]==ans){ ma=max(ma,e[i].cost); }//cout<<f[i]<<" "<<e[i].to<<endl; } /* for(int i=1;i<2*n;i++) cout<<f[i]<<" ";*/ // cout<<endl; //cout<<ans<<endl; // cout<<maa<<" "<<ma<<endl; if(maa-ma>x){ return 1; } else{ return 0; } } int main() { freopen("transport.in","r",stdin); freopen("transport.out","w",stdout); // freopen("1.txt","r",stdin); scanf("%d%d",&n,&m); for(int i=1;i<n;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); edge_add(x,y,z); } init_lca(); int r=1; for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); q[++t].from=x; q[t].to=y; q[t].lc=q_lc(x,y); q[t].cost=dis[x]+dis[y]-2*dis[q[t].lc]; r=max(q[t].cost,r); } int l=1; while(l!=r){//cout<<l<<" "<<r<<endl; int mid=(l+r)>>1; if(check(mid)){ l=mid+1; } else{ r=mid; } } cout<<l; return 0; }