noip2015运输计划

二分+LCA+查分前缀和

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int read()

 {

     int x=,f=;char ch;ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 struct data{int to,next,v,from;}e[];

 struct data2{int to,next,from,num;}as[];

 int lca[],dis[];

 int head[],head2[],cnt;

 void add(int u,int v,int w){e[cnt].from=u,e[cnt].to=v,e[cnt].next=head[u],e[cnt].v=w,head[u]=cnt;cnt++;}

 void add2(int u,int v,int nu){as[cnt].to=v,as[cnt].next=head2[u],as[cnt].from=u,as[cnt].num=nu,head2[u]=cnt,cnt++;}

 int n,m,l=,r=;

 int d[];

 bool vis[];

 int fa[];

 int p[];

 int s[],t1[];

 int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}

 int maxn=,maxj=;

 void dfs(int now,int d)

 {

     dis[now]=d;

     vis[now]=;

     for(int i=head[now];i>=;i=e[i].next) if(!vis[e[i].to]) dfs(e[i].to,d+e[i].v);

 }

 void Lca(int now)

 {

     vis[now]=;

     for(int i=head[now];i>=;i=e[i].next)

         if(!vis[e[i].to])

         {

             Lca(e[i].to);fa[find(e[i].to)]=find(now);

         }

     for(int i=head2[now];i>=;i=as[i].next)

     {

         if(vis[as[i].to])

         {

             lca[as[i].num]=find(as[i].to);

             //cout<<dis[as[i].from]<<' '<<dis[as[i].to]<<' '<<2*dis[lca[as[i].num]]<<endl;

             d[as[i].num]=abs(dis[as[i].from]+dis[as[i].to]-*dis[lca[as[i].num]]);

             r=max(r,d[as[i].num]);

         }

     }

 }

 int work(int now,int t,int from)

 {

     int sum=p[now];

     for(int i=head[now];i>=;i=e[i].next)

         if(e[i].to!=from) sum+=work(e[i].to,t,e[i].from);

     if(sum==t)maxj=max(maxj,dis[now]-dis[from]);

     return sum;

 }

 bool check(int mid,int t)

 {

     work(,t,);

     if(maxn-maxj<=mid) return ;

     else return ;

 }

 int main()

 {

     memset(head,-,sizeof(head));

     memset(head2,-,sizeof(head2));

     n=read(),m=read();

     for(int i=;i<=n;i++) fa[i]=i;

     for(int i=;i<n;i++)

     {

         int u,v,w;

         u=read(),v=read(),w=read();

         add(u,v,w);

         add(v,u,w);

     }

     cnt=;

     for(int i=;i<=m;i++)

     {

         s[i]=read(),t1[i]=read();

         add2(s[i],t1[i],i);

         add2(t1[i],s[i],i);

     }

     dfs(,);

     memset(vis,,sizeof(vis));

     Lca();

     //for(int i=1;i<=n;i++) cout<<dis[i]<<endl;

     //for(int i=1;i<=m;i++) cout<<d[i]<<endl;

     while(l<=r)

     {

         int t=;

         int mid=(l+r)>>;

         maxj=;

         memset(p,,sizeof(p));

         for(int i=;i<=m;i++)

         {

             if(d[i]>mid){maxn=max(maxn,d[i]);t++;p[s[i]]++,p[t1[i]]++,p[lca[i]]-=;}

         }

         if(check(mid,t)) r=mid-;

         else l=mid+;

     }

     cout<<l;

     return ;

 }