BZOJ 1787: [Ahoi2008]Meet 紧急集合

Description

Input

Output

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

solution:
我们分别求三个点中两两的lca，不难发现一定会有两个相同，我们用不同的那个做集合地点就好了。其实我也不知道为什么要用这个，反正A了就是，欢迎大犇告诉我原因。

至于三个点都在同一条链上的情况也是一样。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #define maxn 500010
 6 using namespace std;
 7 struct node{int to,next;}e[maxn*2];
 8 int head[maxn],deep[maxn],fa[maxn],son[maxn],siz[maxn],top[maxn],cnt;
 9 int n,m;
10 void add(int x,int y)
11 {
12     e[++cnt].to=y;e[cnt].next=head[x];head[x]=cnt;
13 }
14 void dfs1(int x)
15 {
16     deep[x]=deep[fa[x]]+1;siz[x]=1;
17     for(int i=head[x];i;i=e[i].next)
18     {
19         int to=e[i].to;
20         if(fa[x]!=to)
21         {
22             fa[to]=x;
23             dfs1(to);
24             siz[x]+=siz[to];
25             if(siz[son[x]]<siz[to]) son[x]=to;
26         }
27     }
28 }
29 void dfs2(int x)
30 {
31     if(x==son[fa[x]]) top[x]=top[fa[x]];
32     else top[x]=x;
33     for(int i=head[x];i;i=e[i].next)
34     if(fa[e[i].to]==x) dfs2(e[i].to);
35 }
36 void inti()
37 {
38     int a,b;
39     scanf("%d%d",&n,&m);
40     for(int i=1;i<n;i++) scanf("%d%d",&a,&b),add(a,b),add(b,a); 
41     dfs1(1);dfs2(1);
42 }
43 int lca(int x,int y)
44 {
45     for(;top[x]!=top[y];deep[top[x]]>deep[top[y]]?x=fa[top[x]]:y=fa[top[y]]);
46     return deep[x]<deep[y]?x:y;
47 }
48 int cc(int x,int y)
49 {
50     int t=lca(x,y);
51     return deep[x]+deep[y]-2*deep[t];
52 } 
53 void work()
54 {
55     int a,b,c,x,y,z,ans,sum;
56     for(int i=1;i<=m;i++) 
57     {
58         scanf("%d%d%d",&x,&y,&z);
59         int p1=lca(x,y),p2=lca(x,z),p3=lca(y,z),t;
60         if(p1==p2)t=p3;
61          else if(p2==p3)t=p1;
62           else t=p2;
63        int ans;
64        ans=cc(x,t)+cc(y,t)+cc(z,t);
65        printf("%d %d
",t,ans);
66     }
67     
68 }
69 int main()
70 {
71     inti();
72     work();
73     return 0;
74 }

View Code

以上by Carrot