运输计划

noip 二分 树上差分

题面

给一棵有$n$个节点的带边权树，现给出$m$个点对，问将哪条边权改为$0$可使每个点对中最大两点间路径边权和最小。

• $20pts\ m=1$
• $60pts\ m,n\leq3000$
• $80pts\ tree->queue$
• $100pts\ n,n\leq3*10^5$
  (下面分值中包含上面分值）

解析

第一眼看题发现可以二分，但不知道怎么$check$。。。
于是沦为攻略部分分的咸鱼

$20pts$算法

预处理树的深度$d[n]$,再暴跳到$LCA$来找边权最大值$max$即可。
$ans=d[u]+d[v]-2*d[lca]-max$
复杂度$O(n)$

$60pts$算法

可以枚举置$0$的那条边，再一一求出两点间距离(要 求$LCA$)。
当然，把一条边置$0$时只要把以儿子点为根的子树的点权都减去该边边权即可。
如果以树的重心为根，可以保证复杂度为$O(n^2logn)$（求$LCA$和子树减边权都是$O(logn)$）

il void dfs1(re int u,re int fa)
{
  sz[u]=1;d[u]=d[fa]+1;
  f[u]=fa;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      df[v]=df[u]+e[i].w;
      dfs1(v,u);
      sz[u]+=sz[v];
      if(sz[son[u]]<sz[v]) son[u]=v;
    }
}
il void dfs2(re int u,re int up)
{
  L[u]=++tim;top[u]=up;id[tim]=u;
  if(son[u]) dfs2(son[u],up);
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==f[u]||v==son[u]) continue;
      dfs2(v,v);
    }
  R[u]=tim;
}
il int getlca(re int u,re int v)
{
  while(top[u]^top[v])
    {
      if(d[top[u]]<d[top[v]]) swap(u,v);
      if(f[top[u]]!=u) u=f[top[u]];
      else break;
    }
  return d[u]<d[v]?u:v;
}
il void ddfs(re int u,re int fa,re int w)
{
  df[u]+=w;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      ddfs(v,u,w);
    }
}
il void dfs(re int u,re int fa)
{
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      sum=0;
      ddfs(v,u,-e[i].w);
      fp(o,1,m)
      {
        re int u=a[o].u,v=a[o].v,lca=getlca(u,v);
        sum=max(sum,df[u]+df[v]-2*df[lca]);
      }
      ans=min(ans,sum);
      ddfs(v,u,e[i].w);
      dfs(v,u);
    }
}
il void getroot(re int u,re int fa)
{
  sz[u]=1;dp[u]=0;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      getroot(v,u);
      sz[u]+=sz[v];
      dp[u]=max(dp[u],sz[v]);
    }
  dp[u]=max(dp[u],n-dp[u]);
  if(dp[u]<dp[rt]) rt=u;
}
il void met1()
{
  re int u=gi(),v=gi(),lca=getlca(u,v);
  sum+=df[u]+df[v]-2*df[lca];
  while(u^lca) {dd=max(dd,df[u]-df[f[u]]);u=f[u];}
  while(v^lca) {dd=max(dd,df[v]-df[f[v]]);v=f[v];}
  printf("%lld\n",sum-dd);
}
il void met2()
{
  fp(i,1,m)
    {
      re int u=gi(),v=gi();
      a[i]=(dat){u,v};
    }
  dfs(1,0);
  printf("%lld\n",ans);
}
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();m=gi();
  fp(i,1,n-1)
    {
      re int u=gi(),v=gi(),w=gi();
      add(u,v,w);add(v,u,w);val[u]=w;
    }
  getroot(rt=1,0);
  dfs1(rt,0);dfs2(rt,rt);
  if(m==1) met1();
  else if(m<=3000&&n<=3000) met2();
  return 0;
}

$80pts$算法

题意显然要求我们二分答案。
怎么$check$呢？怎么看出该把哪条边边权置$0$呢？
我们可以先预处理出所有两点间距离。
此时可以发现有$k$个距离大于$ans$。
那么我们起码要找被这$k$个距离同时经过的边。（没想到这个）

啥，你不知道怎么在树上找？
在该情况下，可以直接用线段树维护边的被经过次数，在此基础上取边权最大值，看最大距离减这个值是否小于等于$ans$后即可。
线段树$O(nlogn)$，二分$O(logn)$，总复杂度$O(nlog^2n)$

（不过如果是要求时间和，可以用线段树维护每条边走了多少次，最后把次数与边权积最大的减掉）

$100pts$算法

可以用树上差分维护边被这$k$个距离经过的次数（当然用点代表该点父边）。
具体是$w[u]$++,$w[v]$++,$w[lca]$-=2。
然后跑$dfs$自下而上统计。
复杂度$O(nlogn)$
（我一开始好像是用树的深度求距离）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define ls x<<1
#define rs x<<1|1
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5+100;
struct Edge{int to,nxt,w;}e[N<<1];
struct dat{ll u,v,w,lca;}a[N<<1];
int n,m,cnt,sz[N],d[N],df[N],f[N],w[N],L[N],R[N],top[N],h[N],id[N],son[N],tim,mx,tag[N];
ll sum,ans=1e18,mxx;
il void add(re int u,re int v,re int w)
{
  e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;
}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void dfs1(re int u,re int fa)
{
  sz[u]=1;d[u]=d[fa]+1;
  f[u]=fa;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
       df[v]=df[u]+e[i].w;
      dfs1(v,u);
      sz[u]+=sz[v];tag[v]=e[i].w;
      if(sz[son[u]]<sz[v]) son[u]=v;
    }
}
il void dfs2(re int u,re int up)
{
  L[u]=++tim;top[u]=up;id[tim]=u;
  if(son[u]) dfs2(son[u],up);
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==f[u]||v==son[u]) continue;
      dfs2(v,v);
    }
  R[u]=tim;
}
il int getlca(re int u,re int v)
{
  while(top[u]^top[v])
    {
      if(d[top[u]]<d[top[v]]) swap(u,v);
      u=f[top[u]];
    }
  return d[u]<d[v]?u:v;
}
il void dfs(re int u,re int fa)
{
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs(v,u);
      w[u]+=w[v];
    }
  if(w[u]==sum&&tag[u]>mx) mx=tag[u];
}
il int check(re ll x)
{
  memset(w,0,sizeof(w));
  sum=0;mx=0;
  fp(i,1,m)
    if(a[i].w>x)
      {
    ++sum;
    re int u=a[i].u,v=a[i].v,lca=a[i].lca;
    ++w[u];++w[v];w[lca]-=2;
      }
  dfs(1,0);
  if(mxx-mx>x) return 0;
  return 1;
}
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();m=gi();
  fp(i,1,n-1)
    {
      re int u=gi(),v=gi(),w=gi();
      add(u,v,w);add(v,u,w);
    }
  dfs1(1,0);dfs2(1,1);
  fp(i,1,m)
    {
      re int u=gi(),v=gi(),lca=getlca(u,v);
      a[i]=(dat){u,v,df[u]+df[v]-2*df[lca],lca};
      mxx=max(mxx,a[i].w);
    }
  re ll l=0,r=mxx,ans=0;//printf("%lld\n",mxx);
  while(l<=r)
    {
      re int mid=l+r>>1;
      if(check(mid)) ans=mid,r=mid-1;
      else l=mid+1;
    }
  printf("%lld\n",ans);
  return 0;
}