Bzoj1787-P4281 [AHOI2008]紧急集合 / 聚会
十分感谢 \(\texttt{darkbzoj}\) 所提供的的数据
没有这个数据我估计调不出来。
description
描述
欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有 n 个等待点，有 n?1 条道路连接着它们，每一条道路都连接某两个等待点，且通过这些道路可以走遍所有的等待点，通过道路从一个点到另一个点要花费一个游戏币。
参加游戏的人三人一组，开始的时候，所有人员均任意分散在各个等待点上（每个点同时允许多个人等待），每个人均带有足够多的游戏币（用于支付使用道路的花费）、地图（标明等待点之间道路连接的情况）以及对话机（用于和同组的成员联系）。当集合号吹响后，每组成员之间迅速联系，了解到自己组所有成员所在的等待点后，迅速在 n 个等待点中确定一个集结点，组内所有成员将在该集合点集合，集合所用花费最少的组将是游戏的赢家。
小可可和他的朋友邀请你一起参加这个游戏，由你来选择集合点，聪明的你能够完成这个任务，帮助小可可赢得游戏吗？
输入格式
第一行两个正整数 n 和 m，分别表示等待点的个数（等待点也从 11 到 nn 进行编号）和获奖所需要完成集合的次数。
随后 n-1n?1 行，每行两个正整数 a,b表示编号为 a 和编号为 b 的等待点之间有一条路。
随后 m 行，每行用三个正整数 x,y,z表示某次集合前小可可、小可可的朋友以及你所在等待点的编号。
输出格式
输出共 m 行，每行两个用空格隔开的整数 p,c。其中第 i 行表示第 i 次集合点选择在编号为 p 的等待点，集合总共的花费是 c 个游戏币。
Input
6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6
Output
5 2
2 5
4 1
6 0
Hint
1<=x,y,z,n,m<=5e5
solution
说实话这个样例给的真的很有迷惑性。
这个数据（↑）让我以为 \(lca(x,lca(y,z))\) 就是 \(p\)。
（当然也因为我没认真读题）
后面手玩了一组数据：
然后回去看样例发现，诶不对啊。
为什么 query_p(4,5,6)=5 ？
然后发现这个是在中间的.
于是我觉得要看三个 \(\texttt{LCA}\) 里面 \(depth\) 最大的那一个。
为什么？
如图，绿边是真正的树边。
很明显我们不是去 \(lca(x,y)\) 集合就是去 \(lca(x,z) \operatorname{or} \,lca(y,z)\)。
那么边 \(\,alpha\, beta\, ceta\) 边都是必须走的。
相当于先让 \(x,y\) 跳到 \(lca(x,y)\) ，让 \(z\) 跳到最上面那个公共的 \(\texttt{LCA}\)
但如果让 \(x,y\) 同时去最上面的话，\(c\) 会加上 \(2\times delta\)。
如果只让 \(z\) 到 \(lca(x,y)\) 的话只会加上 \(delta\)。
明显更优,所以集合点 \(p\) 是深度更大的 \(\texttt{LCA}\)。
那么就把 \(x,y,z\) 的 \(depth\) 分别和这个 \(depth\) 最大的的 \(\texttt{LCA}\) 的 \(depth\) 分别作差然后求和。
（相等就特判）
于是又挂了 
画了下面这个图之后我分析了一下：
假设查询是这样子的
很明显 \(depth\) 最大的那个 \(\texttt{LCA}\) 是 \(y\)
但是 \(depth[z]=depth[y]\) ，而实际上 \(z\) 还要先到 \(root\) 再到 \(y\)去，。
所以深度相等的时候直接减会错。
要稍微改写一下式子。
那么设 \(depth\) 更大的 \(\texttt{LCA}\) 为 \(p\),
设 \(lca(x,z)=rxz,lca(y,z)=ryz,lca(x,y)=rxy(p)\)
\(c=c_x+c_y+c_z\)
\(c_z=dep[z]-dep[root]+dep[p]-dep[root]\)
\(c_x=dep[x]-dep[p]\)
\(c_y=dep[y]-dep[p]\)
那么
\(c=dep[z]-dep[root]+dep[p]-dep[root]+dep[x]-dep[p]+dep[y]-dep[p]\)
\(=dep[x]+dep[z]+dep[y]-dep[p]-2\times dep[root]\)
所以
\(c=dep[x]+dep[y]+dep[z]-dep[p]-dep[ryz]-dep[rxz]\)
\(c=\sum_{i \in \{x,y,z\}} dep[i]-\sum_{j \in \{rxy,rxz,ryz\}} dep[j]\)
因为 \(x,y,z\) 的顺序不影响式子（只需要在code里判一下），所以这就是通项公式。
那么代码就很简单了
#include
using namespace std;
const int si=5e5+8;
int n,m,root;
struct Tree{
int ver,head,Next;
}e[si<<1];
int cnt=0;
void add(int u,int v){
e[++cnt].ver=v;e[cnt].Next=e[u].head;
e[u].head=cnt;
}
int dep[si];
int f[si][20];
void dfs(int i,int fa){
dep[i]=dep[fa]+1;
f[i][0]=fa;
for(register int j=1;j<18;++j){
f[i][j]=f[f[i][j-1]][j-1];
}
for(register int j=e[i].head;j;j=e[j].Next){
int v=e[j].ver;
if(v==fa) continue;
dfs(v,i);
}
}
int lca(int u,int v){
if(dep[u]=0;--i){
if(dep[f[u][i]]>=dep[v]) u=f[u][i];
}
if(u==v) return u;
for(register int i=19;i>=0;--i){
if(f[u][i]!=f[v][i]){
u=f[u][i],v=f[v][i];
}
}
return f[u][0];
}
pair query(int x,int y,int z){
int p,c;
int rxy=lca(x,y),rxz=lca(x,z),ryz=lca(y,z);
int mx=max(max(dep[rxy],dep[rxz]),dep[ryz]);
if(rxy==rxz && rxz==ryz) p=rxy,c=(dep[x]-dep[p])*3;
else if(mx==dep[rxy]) p=rxy;
else if(mx==dep[rxz]) p=rxz;
else if(mx==dep[ryz]) p=ryz;
c=dep[x]+dep[y]+dep[z]-dep[rxy]-dep[ryz]-dep[rxz];
return make_pair(p,c);
}
int main(){
scanf("%d%d",&n,&m);
for(register int i=1,u,v;ians=query(p1,p2,p3);
printf("%d %d\n",ans.first,ans.second);
}
return 0;
}