NOIP2015 运输计划 (树上差分+二分答案)

---恢复内容开始---

题目大意：给你一颗树，你可以把其中一条边的边权改成0，使给定的一些树链的权值和的最大值最小

把lenth定义为未修改边权时的答案

考虑二分答案，如果二分的答案成立，设修改成0的边边权为k，那么所有原链长>mid的链都要被这条边影响，显然这些链存在边权为k的公共边

那么我们二分出一个答案，然后把所有原链长>mid的链在树上打差分来记录每条边被覆盖多少次

如果某条边的满足lenth-边权<=mid 且这条边被覆盖次数==原链长>mid的链数，说明这条边作为0边可行。

会卡常，据说树剖不会被卡但我用了结果还是被卡了。懒得优化了

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #define N 300100

 using namespace std;

 int n,m,cte,mxl,cnt,lth,ct,idd;

 int head[N],sz[N],tp[N],hvy[N],fa[N],dep[N],dif[N],sum[N],d[N],dis[N];

 struct EDGE{

     int to,nxt,val;

 }edge[N*];

 struct FLY{

     int x,y,ff,len;

 }fly[N];

 void edge_add(int u,int v,int w)

 {

     cte++;

     edge[cte].to = v;

     edge[cte].nxt= head[u];

     edge[cte].val= w;

     head[u]=cte;

 }

 int gc()

 {

     int rett=,fh=;char p=getchar();

     while(p<''||p>'') {p=getchar();}

     while(p>=''&&p<='') {rett=rett*+p-'';p=getchar();}

     return rett*fh;

 }

 void dfs_order1(int u,int dad)

 {

     int h=,id=;

     for(int j=head[u];j!=-;j=edge[j].nxt)

     {

         int v=edge[j].to;

         if(v==dad) continue;

         dis[v]=dis[u]+edge[j].val;

         dep[v]=dep[u]+;

         dfs_order1(v,u);

         d[v]=edge[j].val;

         fa[v]=u;

         if(sz[v]>h) h=sz[v],id=v;

         sz[u]+=sz[v];

     }

     sz[u]++;

     if(head[u]==-) return;

     hvy[u]=id;

 }

 void dfs_order2(int u,int dad,int tpp)

 {

     tp[u]=tpp;

     if(hvy[u]) tp[hvy[u]]=tp[u],dfs_order2(hvy[u],u,tpp);

     for(int j=head[u];j!=-;j=edge[j].nxt)

     {

         int v=edge[j].to;

         if(v==dad||v==hvy[u]) continue;

         dfs_order2(v,u,v);

     }

 }

 void dfs_maxlenth(int u,int dad)

 {

     sum[u]+=dif[u];

     for(int j=head[u];j!=-;j=edge[j].nxt)

     {

         int v=edge[j].to;

         if(v==dad) continue;

         dfs_maxlenth(v,u);

         sum[u]+=sum[v];

     }

     if(sum[u]>=ct&&d[u]>mxl) idd=u,mxl=d[u];

 }

 int LCA(int x,int y)

 {

     while(tp[x]!=tp[y])

     {

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

         x=fa[tp[x]];

     }

     return dep[x]<=dep[y]?x:y;

 }

 bool check(int mid)

 {

     memset(sum,,sizeof(sum));

     mxl=,ct=;;

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

         if(fly[i].len>mid)

         {

             sum[fly[i].x]++,sum[fly[i].y]++;

             sum[fly[i].ff]-=;

             ct++;

         }

     dfs_maxlenth(,-);

     if(lth-mxl<=mid) return ;

     else return ;

 }

 int main()

 {

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

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

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

     int x,y,z;

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

     {

         x=gc(),y=gc(),z=gc();

         edge_add(x,y,z);

         edge_add(y,x,z);

     }

     dfs_order1(,-);

     tp[]=;

     dfs_order2(,-,);

     lth=;

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

     {

         fly[i].x=gc(),fly[i].y=gc();

         fly[i].ff=LCA(fly[i].x,fly[i].y);

         fly[i].len=dis[fly[i].x]+dis[fly[i].y]-*dis[fly[i].ff];

         lth=max(lth,fly[i].len);

     }

     int l=,r=;

     r=lth;

     int ret=;

     while(l<r)

     {

         int mid=(l+r)>>;

         if(check(mid)) r=mid,ret=mid;

         else l=mid+;

     }

     printf("%d",ret);

     return ;

 }

---恢复内容结束---

巴特西

NOIP2015 运输计划 (树上差分+二分答案)

最新文章

热门文章