题解 P4281 【[AHOI2008]紧急集合 / 聚会】

command_block · 2018-08-12 21:38:54 · 题解

蒟蒻最近刚学会树链剖分，想找些模板题来~~水积分~~练习下。

然后我就找到了这一题。

作为一个无脑数据结构选手，拿到题的第一件事就是看题解数据范围。

N<=500000，M<=500000

GG...莫非还有O(NlogN)的树剖？

树剖常熟小,跑不满！

怀着一种常数的信仰，我们开始解题：

首先看到题中给的图是一棵树废话

然后看到多次给出树上的三个点

把一个点移动经过一条边需要花费1节操游戏币

求把三个点移动到一起最少需要多少游戏币

易发现这个最优的集合点一定在这三个点互相通达的简单路径上

可能有点难理解(能感性理解的请跳过分界线)

比如这图,e是简单路径外一点

简单路径:

    .
   /
  /
 /  
.

简单路径外一点e:

    .
   /
  /\
 /  \
.     e

这三个点想要到达e点，必须先要来到a点。因为这是一棵树，这三个点到e只分别存在一条道路，三个点能到达a，通过a就能分别到达e，如果~~破壁者~~有另一条道路的话，这就不是树了

     .
    /
   a
  / \
 /   \
.     e

想要到达e点，必须先要来到a点。

很明显，e点比a点劣(既然已经来到a点不如就在a点集合算了)。

这就证明了最优的集合点一定在这三个点互相通达的简单路径上。

上图

a,b,c分别表示三个点

简单路径如图

     .
    / \
   /   \
  / \   \
 /   \   c
a     b

通过~~大眼观察法~~，很容易发现LCA(a,c)==LCA(b,c)

在树上任选三点t1,t2,t3

相信大家都能理解，不能理解的手动模拟一下上面的图拉直，大概长这样 ``` c | | | | / \ / \ a b ``` 很明显了,这三条线段的唯一公共点w就是最优集合地！！！ ``` c | | | | w / \ / \ a b ``` 证明的话还是用反证法(同上，能感性理解的请跳过分界线) 设有一点h不在w处，却比w优(暂且让他待在CW边上，其他的情况把图转一转就好了) ``` c | | h | w / \ / \ a b ``` 拿出初一几何的架势来(~~其他的不会，我才新初二~~)！！ $Cost_h=CH+(AW+WH)+(BW+WH)=(CH+WH)+AW+BW+WH=CW+AW+BW+WH

原先选择w点的花费Cost_w=CW+AW+BW

很明显Cost_h-Cost_w=WH

而WH>0，所以取点h一定比点w劣

看回原图：

     .
    / \
   /   \
  / \   \
 /   \   c
a     b

w点在这里：

      .
     / \
    /   \
   w     \
  / \     \
 /   \     c
a     b

很明显，w是LCA(a,b),LCA(a,c),LCA(b,c)中深度最大的那一个。

相信大家都能理解(~~真的很明显~~)

然后就可以愉快地套板子了~~哈哈哈哈哈哈~~...

统计$CW+AW+BW$：链剖中的两点间路径统计完美，接下来就是~~码码码码农~~ ## NO,Stop！！！这题不带修！题不带修！不带修！带修！修！ ## 根据套路，不带修的树剖都能用倍增解决这题也是如此倍增求某个点深度，某两个点的$LCA$,简单的一匹。 . 下面是~~愉快的~~分类讨论时间设三个点为$t1,t2,t3;$三个点的深度为$d1,d2,d3$。如果$w=LCA(a,b)$最深 ``` . / \ / \ w \ / \ \ / \ c a b ``` 答案为$deep(a)-deep(w)+deep(b)-deep(w)+deep(c)-deep(.)+deep(w)-deep(.)

整理得deep(a)+deep(b)+deep(c)-deep(w)-deep(.)-deep(.)

如果w=LCA(a,c)最深(我不推那么细了)

      .
     / \
    /   \
   w     \
  / \     \
 /   \     b
a     c

答案还是为deep(a)+deep(b)+deep(c)-deep(w)-deep(.)-deep(.)

如果w=LCA(c,b)最深(我不推那么细了)

      .
     / \
    /   \
   w     \
  / \     \
 /   \     a
c     b

答案依旧为deep(a)+deep(b)+deep(c)-deep(w)-deep(.)-deep(.)

综上所述，答案为

deep(a)+deep(b)+deep(c)-$最**深**$LCA$的深度$-$最**浅**$LCA$的深度$*2

此题完结

代码：

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<vector>
#include<cctype>
using namespace std;
int n,t1,t2,t3,q,len,d1,d2,d3,u1,u2,u3,
    f[520500][20],t[520500];
vector<int> g[520500];
bool e[520500];
inline int read()
{
  int X=0; char ch=0,w=0;
  while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
  while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
  return w?-X:X;
}//快速读入
int getdeep(int num)
{
  int k=18,ans=0;
  while(k>=0){
    while(f[num][k])
     {num=f[num][k];ans+=1<<k;}
    k--;
  }return ans;
}//求某个点的深度
int lca(int x,int y)
{
  int k,dx,dy;
  dx=getdeep(x);dy=getdeep(y);
  if (dx>dy){swap(dx,dy);swap(x,y);}
  k=18;
  while(k>=0){
    while(dy-dx>=(1<<k))
     {y=f[y][k];dy-=1<<k;}
    k--;
  }k=18;
  while(k>=0){
    while(f[x][k]!=f[y][k])
     {x=f[x][k];y=f[y][k];}
    k--;
  }
  if (x!=y)x=f[x][0];
  return x;
}//求某两个点的LCA
void dfs(int num)
{
  e[num]=1;
  for (int i=0;i<g[num].size();i++)
   if (e[g[num][i]])
    f[num][0]=g[num][i];
   else dfs(g[num][i]);
}//化无向为有向
int main()
{
  n=read();q=read();
  for (int i=1;i<n;i++){
    t1=read();t2=read();
    g[t1].push_back(t2);
    g[t2].push_back(t1);
  }dfs(1);
  //--------建图--------
  for (register int j=1;j<=18;j++)
   for (register int i=1;i<=n;i++)
    f[i][j]=f[f[i][j-1]][j-1];
  //--------倍增预处理--------
  for (int i=1;i<=q;i++){
    t1=read();t2=read();t3=read();
    u1=lca(t1,t2);
    u2=lca(t2,t3);
    u3=lca(t1,t3);
    d1=getdeep(u1);
    d2=getdeep(u2);
    d3=getdeep(u3);
    if (d1==d2)
      printf("%d ",u3);
    else if (d3==d2)
      printf("%d ",u1);
    else printf("%d ",u2);
    printf("%d\n",getdeep(t1)+getdeep(t2)+getdeep(t3)
                  -min(d1,min(d2,d3))*2-max(d1,max(d2,d3)));
  }
  return 0;
}

代码略丑，各位dalao请见谅