洛谷P2680 运输计划（树上差分+二分）

考虑树上乱搞

首先这是满足二分性质的，如果在某个时间可以完成工作那么比他更长的时间肯定也能完成工作

然后考虑二分，设当前答案为$mid$，如果有一条链的长度大于$mid$，那么这条链上必须得删去一条边。我们可以贪心的删去所有可以删去的边中最长的，然后看看最长边减去删去的边是否小于等于$mid$，如果成立说明可行

然后考虑怎么solve，我们可以用树上差分，就是对于每个点把它看做他父亲到他的边，每个点记录一个$s$，然后对于一条链，两个端点++，lca-=2。如果有一个点的$s$等于大于$mid$的链的条数，说明它被所有的链给覆盖，然后求一个最大值就好了

然后每一条链的lca都要求出来……实际上直接每一条都$O(logn)$求出来也没关系……不过代码里用的是tarjan离线求的，所以复杂度是$O(n+m)$

总复杂度是$O(nlogn)$（复杂度并没有降……直接树剖求LCA可能更省力啊……）

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,:;}

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=3e5+;

 int head[N],Next[N<<],ver[N<<],edge[N<<],tot;

 int hq[N<<],nq[N<<],vq[N<<],tq;

 int dis[N],a[N],fa[N],s[N],vis[N];

 int n,mx,ans,res,num,m;

 struct node{

     int u,v,len,lca;

     node(){}

     node(int u,int v,int len,int lca):u(u),v(v),len(len),lca(lca){}

     inline void solve(){++s[u],++s[v],s[lca]-=;}

 }q[N];

 inline void add(int u,int v,int e){

     ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;

 }

 inline void addq(int u,int v){

     vq[++tq]=v,nq[tq]=hq[u],hq[u]=tq;

 }

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

 void dfs(int u,int fa){

     for(int i=head[u];i;i=Next[i]){

         int v=ver[i];

         if(v!=fa){

             dfs(v,u),s[u]+=s[v];

         }

     }

     if(s[u]==num) cmax(res,a[u]);

 }

 bool check(int x){

     memset(s,,sizeof(s));

     num=res=;

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

     if(q[i].len>x){

         q[i].solve(),++num;

     }

     dfs(,);

     return mx-res<=x;

 }

 void tarjan(int u,int ff){

     for(int i=head[u];i;i=Next[i]){

         int v=ver[i];

         if(v==ff) continue;

         dis[v]=dis[u]+edge[i];

         tarjan(v,u);

         a[v]=edge[i];

         int f1=find(v),f2=find(u);

         if(f1!=f2) fa[f1]=f2;

         vis[v]=;

     }

     for(int i=hq[u];i;i=nq[i]){

         int v=vq[i];

         if(vis[v]){

             int p=(i+)>>,LCA=find(v);

             q[p]=node(u,v,dis[u]+dis[v]-*dis[LCA],LCA);

             cmax(mx,q[p].len);

         }

     }

 }

 int main(){

 //    freopen("testdata.in","r",stdin);

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

     for(int i=,u,v,e;i<n;++i)

     u=read(),v=read(),e=read(),add(u,v,e),add(v,u,e);

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

     for(int i=,u,v;i<=m;++i)

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

     tarjan(,);

     int l=,r=mx,mid;

     while(l<=r){

         mid=(l+r)>>;

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

         else l=mid+;

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

洛谷P2680 运输计划（树上差分+二分）

最新文章

热门文章