题解 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:
```
.
/
a
/ \
/ \
. e
```
想要到达e点,必须先要来到a点。
很明显,e点比a点劣(既然已经来到a点不如就在a点集合算了)。
这就证明了最优的集合点一定在这三个点互相通达的简单路径上。
------------
上图
a,b,c分别表示三个点
简单路径如图
```
.
/ \
/ \
/ \ \
/ \ c
a b
```
通过~~大眼观察法~~,很容易发现$LCA(a,c)==LCA(b,c)$
在树上任选三点t1,t2,t3
$LCA(t1,t2),LCA(t1,t3),LCA(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)$中深度最大的那一个。
相信大家都能理解(~~真的很明显~~)
然后就可以愉快地套板子了~~哈哈哈哈哈哈~~...
------------
$LCA$:已经写了链剖了,就没倍增什么事了
统计$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$
此题完结
代码:
```cpp
// 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请见谅