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

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

阅读量：6642 次

发布时间：2019-06-25

本文共 3582 字，大约阅读时间需要 11 分钟。

This article is made by Jason-Cow.

Welcome to reprint.
But please post the writer's address.

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

题意：

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

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

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

1.链剖

2.树上差分

3.二分

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

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

1 void dfs1(int u,int f){ 2   fa[u]=f,dep[u]=dep[f]+1,siz[u]=1; 3   for(int i=head[u];i;i=E[i].next){ 4     int v=E[i].v; 5     if(v!=f){ 6       w[v]=E[i].w,dis[v]=dis[u]+E[i].w; 7       dfs1(v,u); 8       siz[u]+=siz[v]; 9       if(!son[u]||siz[v]>siz[son[u]])son[u]=v;10     }11   }12 }

dfs1

1 void dfs2(int u,int t){2   dfn[u]=++idx,top[u]=t;3   if(son[u])dfs2(son[u],t);4   for(int i=head[u];i;i=E[i].next){5     int v=E[i].v;6     if(v!=fa[u]&&v!=son[u])dfs2(v,v);7   }8 }

dfs2

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

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

1 void modify(int u,int f){2   for(int i=head[u];i;i=E[i].next){3     int v=E[i].v;4     if(v!=f){5       modify(v,u);6       cf[u]+=cf[v];7     }8   }9 }

modify

二分，很显然好吗。

1 bool check(int x){ 2   int cnt=0,maxcost=0; 3   memset(cf,0,sizeof(cf)); 4   for(int i=1;i<=m;i++) 5     if(a[i].dis>x){ 6       cnt++; 7       maxcost=max(maxcost,a[i].dis-x); 8       cf[a[i].s]++,cf[a[i].t]++;cf[a[i].lca]-=2; 9     }10   if(cnt==0)return false;11   modify(1,0);12   for(int i=1;i<=n;i++)13     if(cf[i]==cnt && w[i]>=maxcost)14       return false;15   return true;16 }

check

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

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
              10 #include 
              
                11 using namespace std; 12 const int N=3e5+10,M=6e5+10; 13 inline void _(int &ans){ 14 ans=0;char x=getchar(),f=0; 15 while(x<'0'||x>'9'){ if(x=='-')f=1;x=getchar();} 16 while(x>='0'&&x<='9')ans=ans*10+x-'0',x=getchar(); 17 if(f)ans=-ans; 18 } 19 20 int head[N],tot,n,m; 21 int dfn[N],top[N],siz[N],son[N],dep[N],fa[N],idx; 22 int dis[N],w[N],cf[N]; 23 struct node{ int v,w,next;}E[M]; 24 struct ask{ int lca,dis,s,t;}a[N]; 25 void add(int u,int v,int w){E[++tot]=(node){v,w,head[u]},head[u]=tot;} 26 void edge(int u,int v,int w){add(u,v,w),add(v,u,w);} 27 28 void dfs1(int u,int f){ 29 fa[u]=f,dep[u]=dep[f]+1,siz[u]=1; 30 for(int i=head[u];i;i=E[i].next){ 31 int v=E[i].v; 32 if(v!=f){ 33 w[v]=E[i].w,dis[v]=dis[u]+E[i].w; 34 dfs1(v,u); 35 siz[u]+=siz[v]; 36 if(!son[u]||siz[v]>siz[son[u]])son[u]=v; 37 } 38 } 39 } 40 41 void dfs2(int u,int t){ 42 dfn[u]=++idx,top[u]=t; 43 if(son[u])dfs2(son[u],t); 44 for(int i=head[u];i;i=E[i].next){ 45 int v=E[i].v; 46 if(v!=fa[u]&&v!=son[u])dfs2(v,v); 47 } 48 } 49 50 void lca(int s,int t,int i){ 51 int x=s,y=t; 52 while(top[x]!=top[y]){ 53 if(dep[top[x]]
               
                dep[y])swap(x,y); 57 a[i].lca=x; 58 a[i].dis=dis[s]+dis[t]-2*dis[x]; 59 } 60 61 void modify(int u,int f){ 62 for(int i=head[u];i;i=E[i].next){ 63 int v=E[i].v; 64 if(v!=f){ 65 modify(v,u); 66 cf[u]+=cf[v]; 67 } 68 } 69 } 70 71 bool check(int x){ 72 int cnt=0,maxcost=0; 73 memset(cf,0,sizeof(cf)); 74 for(int i=1;i<=m;i++) 75 if(a[i].dis>x){ 76 cnt++; 77 maxcost=max(maxcost,a[i].dis-x); 78 cf[a[i].s]++,cf[a[i].t]++;cf[a[i].lca]-=2; 79 } 80 if(cnt==0)return false; 81 modify(1,0); 82 for(int i=1;i<=n;i++) 83 if(cf[i]==cnt && w[i]>=maxcost) 84 return false; 85 return true; 86 } 87 88 int _u,_v,_w,_s,_t; 89 int l,r,mid; 90 int main(){ 91 _(n),_(m);//scanf("%d%d",&n,&m); 92 for(int i=1;i
                
                 >1;107 if(check(mid))l=mid+1;108 else r=mid-1;109 }110 printf("%d\n",l);111 return 0;112 }