洛谷 | P4281 [AHOI2008] 紧急集合 / 聚會#
題目描述#
歡樂島上有個非常好玩的遊戲，叫做「緊急集合」。在島上分散有 N 個等待點，有 N-1 條道路連接著它們，每一條道路都連接某兩個等待點，且通過這些道路可以走遍所有的等待點，通過道路從一個點到另一個點要花費一個遊戲幣。
參加遊戲的人三人一組，開始的時候，所有人員均任意分散在各個等待點上（每個點同時允許多個人等待），每個人均帶有足夠多的遊戲幣（用於支付使用道路的花費）、地圖（標明等待點之間道路連接的情況）以及對話機（用於和同組的成員聯繫）。當集合號吹響後，每組成員之間迅速聯繫，了解到自己組所有成員所在的等待點後，迅速在 N 個等待點中確定一個集結點，組內所有成員將在該集合點集合，集合所用花費最少的組將是遊戲的贏家。
小可可和他的朋友邀請你一起參加這個遊戲，由你來選擇集合點，聰明的你能夠完成這個任務，幫助小可可贏得遊戲嗎？
輸入輸出格式#
輸入格式：#
第一行兩個正整數 N 和 M（N<=500000，M<=500000），之間用一個空格隔開。分別表示等待點的個數（等待點也從 1 到 N 進行編號）和獲獎所需要完成集合的次數。 隨後有 N-1 行，每行用兩個正整數 A 和 B，之間用一個空格隔開，表示編號為 A 和編號為 B 的等待點之間有一條路。 接著還有 M 行，每行用三個正整數表示某次集合前小可可、小可可的朋友以及你所在等待點的編號。
輸出格式：#
一共有 M 行，每行兩個數 P,C，用一個空格隔開。其中第 i 行表示第 i 次集合點選擇在編號為 P 的等待點，集合總共的花費是 C 個遊戲幣。
輸入輸出樣例#
輸入樣例 #1：
6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6
輸出樣例 #1：
5 2
2 5
4 1
6 0
說明#
提示：
40% 的數據中 N<=2000，M<=2000
100% 的數據中，N<=500000，M<=500000
這道題巨難！！
過程#
開始想的是求那三個點的 LCA，結果果然 WA 了。
~~ 同為不過樣例的代碼，怎麼我就一個點沒過呢（滑稽） ~~
後來看了 這個大佬 的題解，過程在原文，結論是：
那個點是 LCA (a,b),LCA (b,c),LCA (a,c) 中深度最大的
花費是 deep (a)+deep (b)+deep (c)? 最深LCA 的深度？最淺LCA 的深度？2（其實就是減 a,b,c 三個深度，因為有兩個 LCA 是一樣的）
“在樹上任選三點 t1,t2,t3，LCA (t1,t2),LCA (t1,t3),LCA (t2,t3) 中一定有兩個是相等的。”
然後，在洛谷上過了，一中 oj 上 TLE 兩個點嘤。
最後用了快讀，加了 inline，都還過不了
Code#
（這份代碼沒用快讀）
#include<bits/stdc++.h>
using namespace std;
const int MAXN=500000*2+5;
int n,m;
struct tu{
private:
struct ed{
int to,nex;
} e[MAXN];
int head[MAXN],newp,siz,root,H,f[MAXN][20];
int depth[MAXN];
bool bfsed;
public:
inline void clear(void){
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
memset(f,0,sizeof(f));
memset(depth,0,sizeof(depth));
newp=0;
siz=0;
root=1;
bfsed=0;
}
inline void vAdd(int p1,int p2){
++newp;
e[newp].to=p2;
e[newp].nex=head[p1];
head[p1]=newp;
}
inline void resize(int s){
siz=s;
H=(int)(1.0*log(siz)/log(2)+0.5);
}
inline int size(void){
return siz;
}
inline int lca(int p1,int p2){
if(!bfsed){
bfs();
}
if(depth[p1]<depth[p2]){
swap(p1,p2);
}
for(int i=H;i>=0;--i){
if(depth[f[p1][i]]>=depth[p2]){
p1=f[p1][i];
}
}
if(p1==p2)return p1;
for(int i=H;i>=0;--i){
if(f[p1][i]!=f[p2][i]){
p1=f[p1][i];
p2=f[p2][i];
}
}
return f[p1][0];
}
inline void solve(int x,int y,int z){
int a,b,c;
a=lca(x,y);
b=lca(y,z);
c=lca(x,z);
int ans1,ans2;
if(depth[a]>=depth[b] && depth[a]>=depth[c]){
ans1=a;
}
else if(depth[b]>=depth[a] && depth[b]>=depth[c]){
ans1=b;
}
else if(depth[c]>=depth[a] && depth[c]>=depth[b]){
ans1=c;
}
int pt1=depth[x]-depth[a];
int pt2=depth[y]-depth[b];
int pt3=depth[z]-depth[c];
ans2=pt1+pt2+pt3;
printf("%d %d\n",ans1,ans2);
}
inline void bfs(void){
queue<int> q;
q.push(root);
depth[root]=1;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=e[i].nex){
int y=e[i].to;
if(depth[y])continue;
depth[y]=depth[x]+1;
f[y][0]=x;
for(int j=1;j<=H;++j){
f[y][j]=f[f[y][j-1]][j-1];
}
q.push(y);
}
}
bfsed=1;
}
};
tu a;
int main(void){
scanf("%d%d",&n,&m);
a.clear();
a.resize(n);
for(int i=1;i<n;++i){
int p1,p2;
scanf("%d%d",&p1,&p2);
a.vAdd(p1,p2);
a.vAdd(p2,p1);
}
for(int i=1;i<=m;++i){
int keke,kaka,waiwai;
scanf("%d%d%d",&keke,&kaka,&waiwai);
a.solve(keke,kaka,waiwai);
}
return 0;
}