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 these roads. It costs one game coin to travel from one point to another through a road.
Three people form a group to participate in the game. At the beginning, all personnel are scattered at various waiting points (multiple people are allowed to wait at each point), and each person carries enough game coins (used to pay for the cost of using the road), a map (indicating the connection between waiting points), and a communication device (used to contact members of the same group). When the assembly signal is sounded, 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, the smart one, 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 the waiting points with numbers A and B. Then there are M lines, each line contains three positive integers representing the number of Little Coco, the number of Little Coco's friend, and the number of the waiting point you are at before the 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 i-th assembly point chosen at the waiting point with number P, 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 data, N<=2000, M<=2000
In 100% of the data, N<=500000, M<=500000
This problem is very difficult!!
Process#
At first, I wanted to find the LCA of those three points, but it turned out to be WA.
The code is the same as the sample, why did I fail (silly)
Then I read the solution from this master, the process is in the original text, and the conclusion is:
The point is the deepest one 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 (actually, it's just subtracting the depths of a, b, and c, because two LCAs are the same)
"Choose any three points t1, t2, t3 on the tree, among LCA(t1,t2), LCA(t1,t3), LCA(t2,t3), there must be two that are equal."
After that, I passed it on Luogu, but failed on another online judge with TLE 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 graph{
private:
struct edge{
int to,next;
} 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].next=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].next){
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;
}
};
graph 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;
}