題目描述
歡樂島上有個非常好玩的游戲，叫做“緊急集合”，在島上分散有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
聽說Tarjan會卡，不知道是不是真的 ，我用的倍增，，
首先，看到題，這題不是很簡單嗎，每次詢問求一個三個點的LCA，再用差分求總路長，
嗯~，模擬一遍發現樣例都過不去，
冷靜分析一波，發現并不是三個點的LCA，而是每兩個點的LCA中的一個，
那么，到底是哪一個呢，，
自己造樣例，模擬后發現，集合點是三個LCA中深度最深的那個（感性理解下，深度最深的LCA做為集合點可以使兩個等待點的距離貢獻變小而另一個等待點的距離貢獻變大，由于變大多少就會變小多少，顯然兩個點的距離變小，一個點變大，總距離就變小），
最后就剩下求距離了，用兩個差分就行，詳細看代碼
#include<cstdio>
#define ri register int
const int maxn=5e5+7;//不要問我為什么加7
struct E{
int to,next;
}e[maxn<<1];
int head[maxn],d[maxn];
int fa[maxn][27];
int lg[maxn];//存log2（i）+1，用的時候減一
int n,m,cnt;
void swap(ri &x,ri &y){ri z=x;x=y,y=z;}//手打swap好像更快
inline int read(){
ri x=0,y=0;
char c=getchar();
while((c<'0'||c>'9')&&(y=c=='-',1)) c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return y?-x:x;
}
inline void add(ri u,ri v){
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs(ri u,ri _fa){
d[u]=d[_fa]+1,fa[u][0]=_fa;
for(ri i=1;i<=lg[d[u]];++i) fa[u][i]=fa[fa[u][i-1]][i-1];
for(ri i=head[u];~i;i=e[i].next) if(e[i].to!=_fa) dfs(e[i].to,u);
}
inline int lca(ri x,ri y){
if(d[x]<d[y]) swap(y,x);
while(d[x]>d[y]) x=fa[x][lg[d[x]-d[y]]-1];//不要忘記減一
if(x==y) return x;
for(ri i=lg[d[x]]-1;i>=0;--i){//這里也要減
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}
int main(){
n=read(),m=read();
for(ri i=1;i<=n;++i) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
for(ri i=1;i<=n;++i) head[i]=-1;
for(ri i=1;i<n;++i){
ri x=read(),y=read();
add(x,y),add(y,x);//鏈式前向星存圖
}
dfs(1,0);
while(m--){
ri x=read(),y=read(),z=read();
ri l1=lca(x,y),l2=lca(x,z),l3=lca(y,z),id=l3;
ri a=y,b=z,c=x;
if(d[l2]>d[id]) id=l2,a=x,b=z,c=y;
if(d[l1]>d[id]) id=l1,a=x,b=y,c=z;//找出最深的LCA
ri ll=lca(id,c);
ri ans=d[a]+d[b]-2*d[id]+d[c]+d[id]-2*d[ll];//求距離和
printf("%d %d\n",id,ans);
}
return 0;
}
思路二：樹剖
先等我打完模板再說
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/231075.html
標籤：其他
上一篇：桂電信科2020程式設計大賽題解