树链剖分-Hello!链剖-[NOIP2015]运输计划-[填坑]

This article is made by Jason-Cow.
Welcome to reprint.
But please post the writer's address.

http://www.cnblogs.com/JasonCow/

[NOIP2015]运输计划 Hello!链剖。你好吗？

题意：

给出一棵n个节点的带权树，m对树上点对

现在允许删除一条边，（权值修改为0）

输出: 最小化的点对间最大距离

1.链剖

2.树上差分

3.二分

链剖我就不多说了,就是两dfs

注意：要在dfs1中多维护一个dis[x]，x到root的距离，顺便记录一下w[x]！

 void dfs1(int u,int f){

   fa[u]=f,dep[u]=dep[f]+,siz[u]=;

   for(int i=head[u];i;i=E[i].next){

     int v=E[i].v;

     if(v!=f){

       w[v]=E[i].w,dis[v]=dis[u]+E[i].w;

       dfs1(v,u);

       siz[u]+=siz[v];

       if(!son[u]||siz[v]>siz[son[u]])son[u]=v;

     }

   }

 }

dfs1

 void dfs2(int u,int t){

   dfn[u]=++idx,top[u]=t;

   if(son[u])dfs2(son[u],t);

   for(int i=head[u];i;i=E[i].next){

     int v=E[i].v;

     if(v!=fa[u]&&v!=son[u])dfs2(v,v);

   }

 }

dfs2

树上差分，先差分，后dfs上放（95分的根本原因，不过好写）

细节：add(l,r) <=> cf[l]++ , cf[r+1]--; 再上放

 void modify(int u,int f){

   for(int i=head[u];i;i=E[i].next){

     int v=E[i].v;

     if(v!=f){

       modify(v,u);

       cf[u]+=cf[v];

     }

   }

 }

modify

二分，很显然好吗。

 bool check(int x){

   int cnt=,maxcost=;

   memset(cf,,sizeof(cf));

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

     if(a[i].dis>x){

       cnt++;

       maxcost=max(maxcost,a[i].dis-x);

       cf[a[i].s]++,cf[a[i].t]++;cf[a[i].lca]-=;

     }

   if(cnt==)return false;

   modify(,);

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

     if(cf[i]==cnt && w[i]>=maxcost)

       return false;

   return true;

 }

check

这个还不是正解，因为被卡常了，于是我就卡数据，嘿嘿嘿～～

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <map>

 #include <set>

 using namespace std;

 const int N=3e5+,M=6e5+;

 inline void _(int &ans){

   ans=;char x=getchar(),f=;

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

   while(x>=''&&x<='')ans=ans*+x-'',x=getchar();

   if(f)ans=-ans;

 }

 int head[N],tot,n,m;

 int dfn[N],top[N],siz[N],son[N],dep[N],fa[N],idx;

 int dis[N],w[N],cf[N];

 struct node{int v,w,next;}E[M];

 struct ask{int lca,dis,s,t;}a[N];

 void add(int u,int v,int w){E[++tot]=(node){v,w,head[u]},head[u]=tot;}

 void edge(int u,int v,int w){add(u,v,w),add(v,u,w);}

 void dfs1(int u,int f){

   fa[u]=f,dep[u]=dep[f]+,siz[u]=;

   for(int i=head[u];i;i=E[i].next){

     int v=E[i].v;

     if(v!=f){

       w[v]=E[i].w,dis[v]=dis[u]+E[i].w;

       dfs1(v,u);

       siz[u]+=siz[v];

       if(!son[u]||siz[v]>siz[son[u]])son[u]=v;

     }

   }

 }

 void dfs2(int u,int t){

   dfn[u]=++idx,top[u]=t;

   if(son[u])dfs2(son[u],t);

   for(int i=head[u];i;i=E[i].next){

     int v=E[i].v;

     if(v!=fa[u]&&v!=son[u])dfs2(v,v);

   }

 }

 void lca(int s,int t,int i){

   int x=s,y=t;

   while(top[x]!=top[y]){

     if(dep[top[x]]<dep[top[y]]) swap(x,y);

     x=fa[top[x]];

   }

   if(dep[x]>dep[y])swap(x,y);

   a[i].lca=x;

   a[i].dis=dis[s]+dis[t]-*dis[x];

 }

 void modify(int u,int f){

   for(int i=head[u];i;i=E[i].next){

     int v=E[i].v;

     if(v!=f){

       modify(v,u);

       cf[u]+=cf[v];

     }

   }

 }

 bool check(int x){

   int cnt=,maxcost=;

   memset(cf,,sizeof(cf));

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

     if(a[i].dis>x){

       cnt++;

       maxcost=max(maxcost,a[i].dis-x);

       cf[a[i].s]++,cf[a[i].t]++;cf[a[i].lca]-=;

     }

   if(cnt==)return false;

   modify(,);

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

     if(cf[i]==cnt && w[i]>=maxcost)

       return false;

   return true;

 }

 int _u,_v,_w,_s,_t;

 int l,r,mid;

 int main(){

   _(n),_(m);//scanf("%d%d",&n,&m);

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

     _(_u),_(_v),_(_w);//scanf("%d%d%d",&_u,&_v,&_w);

     edge(_u,_v,_w);

   }

   dfs1(,);

   dfs2(,);

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

     _(_s),_(_t);//scanf("%d%d",&_s,&_t);

     a[i].s=_s,a[i].t=_t;

     lca(_s,_t,i);

     r=max(r,a[i].dis);

   }

   l=max(,r-);//95分

   while(l<=r){

     int mid=(l+r)>>;

     if(check(mid))l=mid+;

     else          r=mid-;

   }

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

   return ;

 }

巴特西

树链剖分-Hello!链剖-[NOIP2015]运输计划-[填坑]

最新文章

热门文章