LOJ 2553 「CTSC2018」暴力写挂——边分治+虚树

第一棵树上的贡献就是链并，转化成 ( dep[ x ] + dep[ y ] + dis( x, y ) ) / 2 ，就可以在第一棵树上写边分治，把两边的点到第二棵树上建虚树，在虚树上 DP ，那么虚树上的当前点就是它不同子树里点的 lca ，所以记 dp[ cr ][ 0/1 ] 表示该点子树里 “第一棵树边分治的两个点集” 里最大的两个贡献；用当前点的深度作为 “第二棵树的 lca 深度” 来更新答案即可。

一直 TLE 。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

ll Mx(ll a,ll b){return a>b?a:b;}

ll Mn(ll a,ll b){return a<b?a:b;}

const int N=; const ll INF=1e16;

int n,hd[N],xnt=,to[N<<],nxt[N<<],w[N<<],tw;//xnt=1

int siz[N],mn,Rt,p[N],tot; bool vis[N];

ll dep[N],dis[N],ans;

namespace Tr{

  const int K=;

  int hd[N],xnt,to[N<<],nxt[N<<],w[N<<];

  int dfn[N],tim,sta[N],top,pre[N][K+],bin[K+];

  ll dep[N],dp[N][]; int tdp[N];

  bool cmp(int u,int v){return dfn[u]<dfn[v];}

  void add(int x,int y,int z)

  {to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z;}

  void ini_dfs(int cr,int fa)

  {

    dfn[cr]=++tim; dp[cr][]=dp[cr][]=-INF;

    tdp[cr]=tdp[fa]+; pre[cr][]=fa;

    for(int t=,d=fa;(d=pre[d][t-]);t++)

      pre[cr][t]=d;

    for(int i=hd[cr],v;i;i=nxt[i])

      if((v=to[i])!=fa)

    { dep[v]=dep[cr]+w[i]; ini_dfs(v,cr);}

  }

  void init()

  {

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

      {

    u=rdn();v=rdn();z=rdn();

    add(u,v,z); add(v,u,z);

      }

    bin[]=;for(int i=;i<=K;i++)bin[i]=bin[i-]<<;

    ini_dfs(,);

  }

  int get_lca(int x,int y)

  {

    if(tdp[x]<tdp[y])swap(x,y); int d=tdp[x]-tdp[y];

    for(int t=;d;t++)

      if(d&bin[t])x=pre[x][t],d^=bin[t];

    if(x==y)return x;

    for(int t=K;t>=;t--)

      if(pre[x][t]!=pre[y][t])

    x=pre[x][t], y=pre[y][t];

    return pre[x][];

  }

  void link(int cr,int v)

  {

    ans=Mx(ans,((dp[cr][]+dp[v][]+tw)>>)-dep[cr]);

    ans=Mx(ans,((dp[cr][]+dp[v][]+tw)>>)-dep[cr]);

    dp[cr][]=Mx(dp[cr][],dp[v][]);

    dp[cr][]=Mx(dp[cr][],dp[v][]);

    dp[v][]=dp[v][]=-INF;//

  }

  void solve()

  {

    sort(p+,p+tot+,cmp);

    sta[top=]=;//

    for(int i=(p[]==)+;i<=tot;i++)

      {

    int cr=p[i], lca=get_lca(cr,sta[top]);

    while(top&&dfn[lca]<dfn[sta[top]])

      {

        if(dfn[lca]<dfn[sta[top-]])

          link(sta[top-],sta[top]), top--;

        else

          link(lca,sta[top]), top--;

      }

    if(sta[top]!=lca)sta[++top]=lca;

    sta[++top]=cr;

      }

    for(int i=top-;i;i--)link(sta[i],sta[i+]);

    dp[sta[]][]=dp[sta[]][]=-INF;

  }

}

void add(int x,int y,int z){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z;}

void ini_dfs(int cr,int fa)

{

  for(int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=fa)

      { dep[v]=dep[cr]+w[i]; ini_dfs(v,cr);}

}

void get_rt(int cr,int fa,int s)

{

  siz[cr]=;

  for(int i=hd[cr],v;i;i=nxt[i])

    if(!vis[i>>]&&(v=to[i])!=fa)

      {

    get_rt(v,cr,s); siz[cr]+=siz[v];

    int tmp=Mx(siz[v],s-siz[v]);

    if(tmp<mn) mn=tmp, Rt=i;

      }

}

void dfs(int cr,int fa,ll lj,bool fx)

{

  Tr::dp[cr][fx]=lj+dep[cr]; p[++tot]=cr;

  for(int i=hd[cr],v;i;i=nxt[i])

    if(!vis[i>>]&&(v=to[i])!=fa)

      dfs(v,cr,lj+w[i],fx);

}

void solve(int cr,int s)

{

  vis[cr>>]=; tot=;

  dfs(to[cr],,,); dfs(to[cr^],,,);

  tw=w[cr]; Tr::solve();

  int v=to[cr], ts=siz[v];

  if(ts>){ mn=N;get_rt(v,,ts);solve(Rt,ts);}

  v=to[cr^]; ts=s-ts;

  if(ts>){ mn=N;get_rt(v,,ts);solve(Rt,ts);}

}

int main()

{

  n=rdn();

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

    {

      u=rdn();v=rdn();z=rdn();

      add(u,v,z); add(v,u,z);

    }

  Tr::init(); ini_dfs(,);

  mn=N;get_rt(,,n);solve(Rt,n);

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

    ans=Mx(ans,dep[i]-Tr::dep[i]);

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

  return ;

}

以为是常数不够优秀，所以学习了一下别人的代码。http://blog-wayne.com/2018/05/15/509/

　　仔细一想，建虚树的时候每次 logn 地找 lca ，这样岂不是 nlog²n 的？所以不要每次建虚树都找 lca 。

　　一开始把所有 n 个点的相邻点之间的 lca 都找出来。令 a[ i ] 存第一棵树里 dfs 序第 i 大的点的标号， lca[ i ] 存 a[ i ] 和 a[ i-1 ] 的 lca 。

　　边分治的过程中带一个 l , r ，表示现在整个点集对应第二棵树的 a[ l ] ~ a[ r ] 。那么用 lca[ ] 就可以建虚树了。

　　考虑当前点集分成两个之后，怎么更新 a[ ] 和 lca[ ] ；

　　在 a[ ] 中找出所有属于边分治一边的点，假设是 a[ 3 ] , a[ 6 ] , a[ 7 ] ... ，那么 a[ 3 ] 对应的 lca 随便， a[ 6 ] 对应的 lca 应该是 lca[ 4 ] , lca[ 5 ] , lca[ 6 ] 中深度最浅的那个；

　　这样就能在边分治的过程中维护好 a[ ] 和 lca[ ] 了。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define ll long long

#define pb push_back

#define pii pair<int,int>

#define mkp make_pair

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

ll Mn(ll a,ll b){return a<b?a:b;}

ll Mx(ll a,ll b){return a>b?a:b;}

const int N=<<; const ll INF=1e15;

int n,hd[N],xnt=,to[N<<],nxt[N<<],w[N<<];

int mn,siz[N],Rt; ll ans,dp2[N],dp[N][]; bool lx[N];

vector<pii> vt[N];

namespace Tr{

  int hd[N],xnt,to[N<<],nxt[N<<],w[N<<],tim;

  int dep[N],a[N],ta[N],lca[N],tlca[N];

  int sta[N],top; ll dp2[N];

  void add(int x,int y,int z)

  {to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z;}

  void ini_dfs(int cr,int fa)

  {

    while(top&&dep[sta[top]]>=dep[cr])top--;

    a[++tim]=cr; lca[tim]=sta[top]; sta[++top]=cr;

    dp[cr][]=dp[cr][]=-INF;

    for(int i=hd[cr],v;i;i=nxt[i])

      if((v=to[i])!=fa)

    {

      dep[v]=dep[cr]+; dp2[v]=dp2[cr]+w[i];

      ini_dfs(v,cr);

    }

  }

  void init()

  {

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

      u=rdn(),v=rdn(),z=rdn(),add(u,v,z),add(v,u,z);

    ini_dfs(,);

  }

  void link(int cr,int v,int tw)

  {

    ans=Mx(ans,((dp[cr][]+dp[v][]+tw)>>)-dp2[cr]);

    ans=Mx(ans,((dp[cr][]+dp[v][]+tw)>>)-dp2[cr]);

    dp[cr][]=Mx(dp[cr][],dp[v][]);

    dp[cr][]=Mx(dp[cr][],dp[v][]);

    dp[v][]=dp[v][]=-INF;

  }

  int solve(int l,int r,int tw)

  {

    sta[top=]=a[l];

    for(int i=l+;i<=r;i++)

      {

    int lm=dep[lca[i]];

    while(top&&dep[sta[top]]>lm)

      if(dep[sta[top-]]>lm)

        link(sta[top-],sta[top],tw), top--;

      else

        link(lca[i],sta[top],tw), top--;

    if(sta[top]!=lca[i])sta[++top]=lca[i];

    sta[++top]=a[i];

      }

    for(int i=top-;i;i--)link(sta[i],sta[i+],tw);

    dp[sta[]][]=dp[sta[]][]=-INF;

    int mid=l-;

    for(int i=l,tl=;i<=r;i++)

      {

    if(!tl||dep[lca[i]]<dep[tl])tl=lca[i];

    if(!lx[a[i]])

      { ta[++mid]=a[i]; tlca[mid]=tl; tl=;}

      }

    int ret=mid;

    for(int i=l,tl=;i<=r;i++)

      {

    if(!tl||dep[lca[i]]<dep[tl])tl=lca[i];

    if(lx[a[i]])

      { ta[++mid]=a[i]; tlca[mid]=tl; tl=;}

      }

    for(int i=l;i<=r;i++)a[i]=ta[i];

    for(int i=l;i<=r;i++)lca[i]=tlca[i];

    return ret;

  }

}

void add(int x,int y,int z)

{

  to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z;

  to[++xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;w[xnt]=z;

}

void del_ed(int x,int y)

{

  if(to[hd[x]]==y)hd[x]=nxt[hd[x]];

  else

    {

      for(int i=hd[x],pr;i;pr=i,i=nxt[i])

    if(to[i]==y)nxt[pr]=nxt[i];

    }

  if(to[hd[y]]==x)hd[y]=nxt[hd[y]];

  else

    {

      for(int i=hd[y],pr;i;pr=i,i=nxt[i])

    if(to[i]==x)nxt[pr]=nxt[i];

    }

}

void Rbuild(int cr,int fa)

{

  for(int i=,lst=,lm=vt[cr].size();i<lm;i++)

    {

      int v=vt[cr][i].first, z=vt[cr][i].second;

      if(v==fa)continue;

      if(!lst)add(cr,v,z),lst=cr;

      else{ n++; add(lst,n,); add(n,v,z); lst=n;}

    }

  for(int i=,v,lm=vt[cr].size();i<lm;i++)

    if((v=vt[cr][i].first)!=fa) Rbuild(v,cr);

}

void ini_dfs(int cr,int fa)

{

  for(int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=fa)

      { dp2[v]=dp2[cr]+w[i]; ini_dfs(v,cr);}

}

void get_rt(int cr,int fa,int s)

{

  siz[cr]=;

  for(int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=fa)

      {

    get_rt(v=to[i],cr,s); siz[cr]+=siz[v];

    int mx=Mx(siz[v],s-siz[v]);

    if(mx<mn)mn=mx,Rt=i;

      }

}

void dfs(int cr,int fa,ll lj,bool fx)

{

  dp[cr][fx]=lj+dp2[cr]; dp[cr][!fx]=-INF; lx[cr]=fx;

  for(int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=fa) dfs(v,cr,lj+w[i],fx);

}

void solve(int cr,int s,int l,int r)

{

  int u=to[cr^], v=to[cr]; del_ed(u,v);

  dfs(u,,,); dfs(v,,,);

  int mid=Tr::solve(l,r,w[cr]);

  int ts=siz[v];

  if(ts>){mn=N;get_rt(v,,ts);solve(Rt,ts,mid+,r);}

  ts=s-ts;

  if(ts>){mn=N;get_rt(u,,ts);solve(Rt,ts,l,mid);}

}

int main()

{

  n=rdn();

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

    {

      u=rdn();v=rdn();z=rdn();

      vt[u].pb(mkp(v,z)); vt[v].pb(mkp(u,z));

    }

  Tr::init(); int yn=n;

  Rbuild(,); ini_dfs(,);

  mn=N;get_rt(,,n);solve(Rt,n,,yn);

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

    ans=Mx(ans,dp2[i]-Tr::dp2[i]);

  printf("%lld\n",ans); return ;

}

　　后来发现之前 TLE 是忘了写 rebuild ... 不过懒得改了。