-LCA-前缀和-差分-[BZOJ 1832][AHOI2008]聚会

题目描述

Y岛风景美丽宜人，气候温和，物产丰富。Y岛上有N个城市，有N-1条城市间的道路连接着它们。每一条道路都连接某两个城市。幸运的是，小可可通过这些道路可以走遍Y岛的所有城市。神奇的是，乘车经过每条道路所需要的费用都是一样的。小可可，小卡卡和小YY经常想聚会，每次聚会，他们都会选择一个城市，使得3个人到达这个城市的总费用最小。由于他们计划中还会有很多次聚会，每次都选择一个地点是很烦人的事情，所以他们决定把这件事情交给你来完成。他们会提供给你地图以及若干次聚会前他们所处的位置，希望你为他们的每一次聚会选择一个合适的地点。

输入格式

第一行两个正整数，N和M。分别表示城市个数和聚会次数。后面有N-1行，每行用两个正整数A和B表示编号为A和编号为B的城市之间有一条路。城市的编号是从1到N的。再后面有M行，每行用三个正整数表示一次聚会的情况：小可可所在的城市编号，小卡卡所在的城市编号以及小YY所在的城市编号。

输出格式

一共有M行，每行两个数Pos和Cost，用一个空格隔开。表示第i次聚会的地点选择在编号为Pos的城市，总共的费用是经过Cost条道路所花费的费用。

样例输入

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

样例输出

5 2
2 5
4 1
6 0

说明

100%的数据中，N<=500000，M<=500000。

40%的数据中N<=2000，M<=2000。

Solution

一眼就能看出这肯定是个求LCA的问题，但是，这个题不是那么单纯地求LCA，因为一共有三个人，所以我们还要稍微运用一下前缀和/差分的知识

（依然坚持用倍增求LCA）

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#define MAXN 1000010
#define LOG 30
int anc[MAXN << 1][LOG];
int val[MAXN << 1] , dep[MAXN << 1] , len , ecnt , x , y , z , u , v , s , p , n , m , head[MAXN] , h , l , fa[MAXN];
int dis[MAXN];
struct Edge {
    int v , nx , w;
}e[MAXN];
inline void add(int f , int t , int w) {
    e[++ecnt] = (Edge){t , head[f] , w};
    head[f] = ecnt;
}
void dfs(int u , int p , int d) {
    anc[u][0] = p;
    dep[u] = d;
    for (int i = head[u] ; i ; i = e[i].nx) {
        int to = e[i].v;
        if (to == p) continue;
        dis[to] = dis[u] + e[i].w;
        dfs(to , u , d + 1);
    }
}
inline void init(int r , int n) {
    dis[r] = 0;
    dfs(r , 0 , 1);
    for (int j = 1 ; j < LOG ; j++) {
        for (int i = 1 ; i <= n ; i++) {
            anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
}
inline int query(int x , int y) {
    if (dep[x] < dep[y]) std::swap(x , y);
    h = dep[x] - dep[y];
    for (int i = 0 ; h > 0 ; i++) {
        if (h & 1) x = anc[x][i];
        h >>= 1;
    }
    if (x == y) return x;
    for (int i = LOG - 1 ; i >= 0 ; i--) {
        if (anc[x][i] != anc[y][i]) {
            x = anc[x][i];
            y = anc[y][i];
        }
    }
    return anc[x][0];
}
int main() {
    scanf("%d%d" , &n , &m);
    for (int i = 1 ; i < n ; i++) {
        scanf("%d%d" , &u , &v);
        add(u , v , 1);
        add(v , u , 1);
        fa[u]++;
        fa[v]++;
    }
    for (int i = 1 ; i <= n ; i++){
        if (fa[i] == 1) {
            s = i;
            break;
        }
    }
    init(s , n);
    for (int i = 1 ; i <= m ; i++) {
        scanf("%d%d%d" , &x , &y , &z);
        int a1 = query(x , y);
        int a2 = query(x , z);
        int a3 = query(y , z);
        if (a1 == a2) {
            l = a3;
        }
        else if (a1 == a3) {
            l = a2;
        }
        else if (a2 == a3) {
            l = a1;
        }
        p = dep[x] + dep[y] + dep[z] - dep[a1] - dep[a2] - dep[a3];
        printf("%d %d\n" , l , p);
    }
}