这道题不难，就是3个点的lca。算法有点多，写成树链剖分的吧！跑完2400多毫秒。还好，挺顺利的，加油！努力啊！注意看数据范围！相信自己，能行的

1 #include
     
       2 #include
      
        3 #include
       
         4 #define rep(i,j,k) for(int i = j; i <= k; i++) 5 #define down(i,j,k) for(int i = j; i >= k; i--) 6 #define maxn 500005 7 using namespace std; 8  9 struct edge{10 int to; edge* next;11 };12 edge* head[500005], *pt, edges[1000005];13 14 void add_edge(int x,int y)15 {16     pt->to = x, pt->next = head[y], head[y] = pt++;17     pt->to = y, pt->next = head[x], head[x] = pt++;18 }19 20 inline int read()21 {22     int s = 0, t = 1; char c = getchar();23     while( !isdigit(c) ){24         if( c == '-' ) t = -1; c = getchar();25     }26     while( isdigit(c) ){27         s = s * 10 + c - '0'; c = getchar();28     }29     return s * t;30 }31 32 int top[maxn], dep[maxn], pa[maxn], size[maxn], son[maxn];33 34 void dfs(int now)35 {36     son[now] = 0, size[now] = 1;37     for(edge*i = head[now]; i; i=i->next){38         int to = i->to; if( to == pa[now] ) continue;39         pa[to] = now, dep[to] = dep[now] + 1;40         dfs(to);41         if( size[to] > size[son[now]] ) son[now] = to;42     }43 }44 45 void dfs2(int now,int ph)46 {47     top[now] = ph;48     if( son[now] ) dfs2(son[now],ph);49     for(edge*i = head[now]; i; i=i->next){50         int to = i->to; if( to == pa[now] || to == son[now] ) continue;51         dfs2(to,to);52     }53 }54 55 int lca(int x,int y)56 {57     while( top[x] != top[y] ){58         if( dep[top[x]] < dep[top[y]] ) swap(x,y);59         x = pa[top[x]];60     }61     if(dep[x] < dep[y] ) return x;62     else return y;63 }64 65 int main()66 {67     int n = read(), m = read(); pt = edges; 68     rep(i,1,n-1){69         int x = read(), y = read();70         add_edge(x,y);71     }72     dep[1] = 0; dfs(1); dfs2(1,1);73     rep(i,1,m){74         int x = read(), y = read(), z = read();75         int lc1 = lca(x,y), lc2 = lca(y,z), lc3 = lca(x,z);76         if( lc1 == lc2 ){77             printf("%d %d\n",lc3,dep[y]-dep[lc1]+dep[x]-dep[lc1]+dep[z]-dep[lc3]);78         }79         else if( lc2 == lc3 ){80             printf("%d %d\n", lc1,dep[z]-dep[lc2]+dep[y]-dep[lc2]+dep[x]-dep[lc1]);81         }82         else if( lc1 == lc3 ){83             printf("%d %d\n", lc2,dep[x]-dep[lc1]+dep[y]-dep[lc1]+dep[z]-dep[lc2]);84         }85     }86     return 0;87 }
       
      
     

1787: [Ahoi2008]Meet 紧急集合

Time Limit: 20 Sec  Memory Limit: 162 MB

Submit: 1829  Solved: 846

[][][]

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

Source