bzoj 1787 [Ahoi2008]Meet 紧急集合(1832 [AHOI2008]聚会)

时间:2021-02-13 04:08:52

1787: [Ahoi2008]Meet 紧急集合

Time Limit: 20 Sec  Memory Limit: 162 MB
Submit: 1841  Solved: 857
[Submit][Status][Discuss]

Description

bzoj 1787 [Ahoi2008]Meet 紧急集合(1832 [AHOI2008]聚会)

Input

bzoj 1787 [Ahoi2008]Meet 紧急集合(1832 [AHOI2008]聚会)

Output

bzoj 1787 [Ahoi2008]Meet 紧急集合(1832 [AHOI2008]聚会)

Sample Input

6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6

Sample Output

5 2
2 5
4 1
6 0

HINT

bzoj 1787 [Ahoi2008]Meet 紧急集合(1832 [AHOI2008]聚会)

Source

【思路】

Lca。

求出三点之间的lca,会出现两个点相同的情况,集合点为另外一个点。

【代码】

 /**************************************************************
Problem: 1787
User: hahalidaxin2
Language: C++
Result: Accepted
Time:3716 ms
Memory:65216 kb
****************************************************************/ #include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<iostream>
using namespace std; const int maxn = +;
const int maxd = ; struct Edge{ int u,v;
};
vector<int> G[maxn];
vector<Edge> es; int d[maxn];
int p[maxn][maxd]; void addedge(int u,int v) {
es.push_back((Edge){u,v});
int m=es.size(); G[u].push_back(m-);
}
void dfs(int u,int fa) {
for(int i=;i<=maxd;i++) { //构造倍增数组
if(d[u]<(<<i)) break;
p[u][i]=p[p[u][i-]][i-];
}
for(int i=;i<G[u].size();i++) {
Edge e=es[G[u][i]]; int v=e.v;
if(v!=fa)
d[v]=d[u]+ , p[v][]=u , dfs(v,u);
}
}
int lca(int u,int v) {
if(d[v]>d[u]) swap(u,v);
int dep=d[u]-d[v];
for(int i=;i<maxd;i++)
if((<<i)&dep) u=p[u][i];
if(u==v) return u;
for(int i=maxd-;i>=;i--)
if(p[u][i]!=p[v][i])
u=p[u][i] , v=p[v][i];
return p[u][];
}
int dist(int x,int y) { return d[x]+d[y]-(d[lca(x,y)]<<); }
int n,m; void read(int& x) {
char c=getchar();
while(!isdigit(c)) c=getchar();
x=;
while(isdigit(c))
x=x*+c-'' , c=getchar();
}
int main() {
read(n),read(m);
int u,v;
for(int i=;i<n-;i++) {
read(u),read(v);
addedge(u,v); addedge(v,u);
}
dfs(n>>,-);
int a,b,c,lab,lac,lbc,s;
while(m--) {
read(a),read(b),read(c);
lab=lca(a,b),lac=lca(a,c),lbc=lca(b,c);
if(lab==lac) s=lbc;
else if(lab==lbc) s=lac;
else s=lab;
printf("%d %d\n",s,dist(a,s)+dist(b,s)+dist(c,s));
}
return ;
}