洛谷 | P4281 [AHOI2008] 緊急集合 / 集会#
問題の説明#
楽しい島には「緊急集合」という非常に面白いゲームがあります。島には N 個の待機ポイントが散らばっており、N-1 本の道路がそれらをつなげています。各道路は特定の 2 つの待機ポイントを結び、これらの道路を通じてすべての待機ポイントにアクセスできます。道路を通って 1 つのポイントから別のポイントに移動するには、1 ゲームコインが必要です。
ゲームに参加する人は 3 人 1 組で、最初はすべての人が任意に各待機ポイントに散らばっています（各ポイントには同時に複数の人が待機できます）。各人は十分なゲームコイン（道路の使用料を支払うため）、地図（待機ポイント間の道路接続状況を示す）および対話機（同じグループのメンバーと連絡を取るため）を持っています。集合の合図が鳴った後、各グループのメンバーは迅速に連絡を取り合い、自分のグループのすべてのメンバーがどの待機ポイントにいるかを把握し、N 個の待機ポイントの中から集合地点を迅速に決定します。集合にかかる費用が最も少ないグループがゲームの勝者となります。
小可可と彼の友人はあなたをこのゲームに招待し、あなたが集合地点を選ぶ役割を担います。賢いあなたはこのタスクを達成し、小可可がゲームに勝つのを助けることができるでしょうか？
入力出力フォーマット#
入力フォーマット：#
最初の行には 2 つの正整数 N と M（N<=500000、M<=500000）が空白で区切られて表示されます。これは待機ポイントの数（待機ポイントは 1 から N まで番号が付けられています）と、賞を得るために完了する必要がある集合の回数を示します。続いて N-1 行があり、各行には 2 つの正整数 A と B が空白で区切られて表示され、A 番と B 番の待機ポイントの間に道路があることを示します。次に M 行があり、各行には 3 つの正整数が表示され、特定の集合の前に小可可、小可可の友人、そしてあなたがいる待機ポイントの番号を示します。
出力フォーマット：#
合計で M 行あり、各行には 2 つの数 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
この問題は非常に難しいです！！
プロセス#
最初に考えたのはその 3 つのポイントの LCA を求めることでしたが、結果的に WA になりました。
~~ 同じくサンプルのコードですが、どうして私は 1 つのポイントも通過できなかったのか（滑稽） ~~
その後、この大佬の解法を見て、プロセスは原文にあり、結論は：
そのポイントは LCA (a,b),LCA (b,c),LCA (a,c) の中で深さが最も大きい
費用は deep (a)+deep (b)+deep (c)? 最深LCA の深さ？最浅LCA の深さ？2（実際には a,b,c の 3 つの深さを引くことになります。なぜなら 2 つの LCA は同じだからです）
「木の上で任意の 3 点 t1,t2,t3 を選ぶと、LCA (t1,t2),LCA (t1,t3),LCA (t2,t3) の中には必ず 2 つが等しい。」
その後、洛谷で通過し、一中 oj では TLE の 2 ポイントが出ました。
最後に速読を使い、inline を追加しましたが、まだ通過できませんでした。
コード#
（このコードは速読を使用していません）
#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;
}