Luogu | P4281 [AHOI2008] Emergency Assembly / Gathering#
Problem Description#
There is a very fun game on Joy Island called "Emergency Assembly". There are N waiting points scattered on the island, and they are connected by N-1 roads. Each road connects two waiting points, and all waiting points can be reached by walking through these roads. It costs one game coin to travel from one point to another through a road.
Three people form a group to play the game. At the beginning, all members are randomly distributed among the waiting points (multiple people can wait at the same point), and each person carries enough game coins (used to pay for the cost of using the roads), a map (indicating the connection of roads between waiting points), and a communication device (used to contact other members of the group). When the assembly signal is blown, the members of each group quickly contact each other and determine the assembly point among the N waiting points. All members of the group will gather at the assembly point, and the group with the minimum total cost of assembly will be the winner of the game.
Little Coco and his friends invite you to participate in this game and ask you to choose the assembly point. Can you, as a smart person, complete this task and help Little Coco win the game?
Input and Output Format#
Input Format:#
The first line contains two positive integers N and M (N<=500000, M<=500000), separated by a space. They represent the number of waiting points (numbered from 1 to N) and the number of times the assembly needs to be completed. Then there are N-1 lines, each line contains two positive integers A and B, separated by a space, indicating that there is a road between waiting point A and waiting point B. After that, there are M lines, each line contains three positive integers indicating the waiting point numbers of Little Coco, Little Coco's friend, and you before each assembly.
Output Format:#
There are M lines in total, each line contains two numbers P and C, separated by a space. The i-th line represents the assembly point for the i-th assembly, and the total cost of the assembly is C game coins.
Input and Output Examples#
Input Example #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
Output Example #1:
5 2
2 5
4 1
6 0
Explanation#
Hint:
In 40% of the test cases, N<=2000 and M<=2000.
In 100% of the test cases, N<=500000 and M<=500000.
This problem is very difficult!!
Process:
At first, I wanted to find the LCA of the three points, but it turned out to be WA (Wrong Answer).
The code is the same as the sample code, why did I fail with just one point (silly)
Later, I read the solution from this expert. The process is in the original text, and the conclusion is:
The point is the deepest among LCA(a,b), LCA(b,c), LCA(a,c)
The cost is deep(a) + deep(b) + deep(c) - the depth of the deepest LCA - the depth of the shallowest LCA + 2 (which is actually subtracting the depths of the three points, because two LCA are the same)
"Choose any three points t1, t2, t3 on the tree, there must be two LCA that are equal."
Then, I passed the test on Luogu, but failed on another online judge with TLE (Time Limit Exceeded) for two points.
Finally, I used fast input and added inline, but still couldn't pass.
Code#
(This code doesn't use fast input)
#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;
}