题解 P4178 【Tree】

ysner · 2018-02-21 16:27:53 · 题解

点分治模板题，大部分和模板1是一样的。

然后我天真地把我原来的代码的答案数组求了个前缀和就交了上去。。。T得不要不要的。。。

il void getroot(re int u,re int fa)
{
  sz[u]=1;f[u]=0;
  for(re int i=h[u];i;i=e[i].next)
    {
      re int v=e[i].to;
      if(v==fa||vis[v]) continue;
      getroot(v,u);//
      sz[u]+=sz[v];
      f[u]=max(f[u],sz[v]);//f[u]存该点以下最大子树
    }
  f[u]=max(f[u],sum-sz[u]);//肯定儿子要比爸爸多啊
  if(f[u]<f[root]) root=u;
}
il void calc(re int u,re int dd,re int add)
{
  cnt=0;d[u]=dd;
  getdeep(u,0);
  fp(i,1,cnt)
    fp(j,1,cnt)
    ans[o[i]+o[j]]+=add;//时间复杂度过高
}
il void work(re int u)
{
  calc(u,0,1);vis[u]=1;
  for(re int i=h[u];i;i=e[i].next)
    {
      re int v=e[i].to;
      if(vis[v]) continue;
      calc(v,e[i].w,-1);
      sum=sz[v];root=0;
      getroot(v,0);//
      work(root);
    }
}

认真分析题目，发现我们在求距离大于k的点对数上花费了大量的时间，并且点对计数用二层循环时间复杂度太高。

所以我们要在优化点对计数数过程下手。

对于根节点进行一次dfs，求出deep，并将其从小到大排序。（longn预处理省一层循环）

避免重复，只需要求出x<y的前提下deep[x]+deep[y]≤k的个数。

用i表示左指针，j表示右指针，i从左向右遍历，j从右向左。

如果deep[i]+deep[j]≤k，则点对(i,t)(i<t≤j)都符合题意，将j-i加入答案中，并且i++；否则j--。

然而这样还会重复计算在同一棵子树中的点对，所以再进行下一步dfs之前需要减去重复部分。

这样就能保证时间复杂度在O(nlog2n)以下。（而不是原来的O（n2long2n))

il void getroot(re int u,re int fa)
{
  sz[u]=1;f[u]=0;
  for(re int i=h[u];i;i=e[i].next)
    {
      re int v=e[i].to;
      if(v==fa||vis[v]) continue;
      getroot(v,u);//
      sz[u]+=sz[v];
      f[u]=max(f[u],sz[v]);
    }
  f[u]=max(f[u],sum-sz[u]);
  if(f[u]<f[root]) root=u;
}
il int calc(re int u)
{
  cnt=0;getdeep(u,0);sort(o+1,o+cnt+1);
  re int i=1,j=cnt,sum=0;
  while(i<j)
    if(o[i]+o[j]<=k) sum+=j-i,i++;
    else j--;//优化后的点对计数过程
  return sum;
}
il void work(re int u)
{
  d[u]=0;vis[u]=1;ans+=calc(u);
  for(re int i=h[u];i;i=e[i].next)
    {
      re int v=e[i].to;
      if(vis[v]) continue;
      d[v]=e[i].w;
      ans-=calc(v);//去重
      sum=sz[v];root=0;
      getroot(v,0);//重选重心
      work(root);
    }
}