比赛 |
近期练习题回顾 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
运输计划 |
最终得分 |
100 |
用户昵称 |
梦那边的美好ET |
运行时间 |
5.217 s |
代码语言 |
C++ |
内存使用 |
82.62 MiB |
提交时间 |
2018-10-31 07:43:00 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>b[300010],c[300010];
int a1,a2,a3,n,m,fa[300010][21],s[300010][21],sd[300010];
int x[300010],y[300010],lc[300010],le[300010],k=0,ma=0,l,r,ans;
int f[300010];
bool bk[300010];
inline void dfs(int p){bk[p]=1;
for(int i=1;i<=20;i++){
fa[p][i]=fa[fa[p][i-1]][i-1];
s[p][i]=s[p][i-1]+s[fa[p][i-1]][i-1];
}
for(int i=0;i<b[p].size();i++){
if(!bk[b[p][i]]){
fa[b[p][i]][0]=p;s[b[p][i]][0]=c[p][i];sd[b[p][i]]=sd[p]+1;
dfs(b[p][i]);
}
}
return;
}
inline void dp(int p){bk[p]=1;
for(int i=0;i<b[p].size();i++){
if(!bk[b[p][i]]){
dp(b[p][i]);
f[p]+=f[b[p][i]];
}
}
return;
}
inline int ju(int w){
int sum=0;
for(int i=1;i<=n;i++)f[i]=bk[i]=0;
for(int i=1;i<=m;i++){
if(w<le[i]){
sum++;
f[x[i]]++;f[y[i]]++;f[lc[i]]-=2;;
}
}
if(sum==0)return 1;
dp(1);
for(int i=2;i<=n;i++)
if(f[i]==sum&&ma-s[i][0]<=w)
return 1;
return 0;
}
inline int lca(int s1,int s2){
a1=s1;a2=s2;
if(sd[a1]<sd[a2]){int fz=a1;a1=a2;a2=fz;}
int p=sd[a1]-sd[a2];
for(int i=20;i>=0;i--){
if((1<<i)<=p){
p-=(1<<i);
le[k]+=s[a1][i];
a1=fa[a1][i];
}
}
if(a1==a2)return a1;
for(int i=20;i>=0;i--){
if(fa[a1][i]!=fa[a2][i]){
le[k]=le[k]+s[a1][i]+s[a2][i];
a1=fa[a1][i];a2=fa[a2][i];
}
}
le[k]=le[k]+s[a1][0]+s[a2][0];
return fa[a1][0];
}
int main(){
freopen("transport.in","r",stdin);
freopen("transport.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
scanf("%d%d%d",&a1,&a2,&a3);
b[a1].push_back(a2);b[a2].push_back(a1);
c[a1].push_back(a3);c[a2].push_back(a3);
}
dfs(1);
for(int i=1;i<=m;i++){k=i;
scanf("%d%d",&x[i],&y[i]);
lc[i]=lca(x[i],y[i]);
ma=max(ma,le[i]);
}
l=0;r=ma;
while(l<=r){
int mid=(l+r)>>1;
if(ju(mid))ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d",ans);
return 0;
}