Acfboy702, MAYDAY.

一道题。

输入一个森林，求两点最短路，不存在路径则输出"No connected"

多组数据，每组输入点数，边数和问题数。

做法：树上倍增求LCA，在用根到两点的距离减去两倍LCA到根的距离。前面用并查集处理是否在同一树上。

我好奔溃啊！！

Code:

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int  fa[100005], vet[100005], nxt[100005], lo[100005], road[100005], head[100005], 
          f[100005][20], dis[100005];
int  n, m, c, Case, x, y, d, num; 
void add(int u, int v, int d){
    num++;
    vet[num] = v;
    nxt[num] = head[u];
    head[u] = num;
    lo[num] = d;
}
int  findfa(int x){
	if(fa[x] != x) fa[x] = findfa(fa[x]);
	return fa[x];
}
void make(int fat, int u, int deep){
    dis[u] = deep;
    for(int now = head[u];  now; now = nxt[now]){
        int v = vet[now];
        if(v == fat) continue;
        road[v] = road[u] + lo[now];
        make(u, v, deep+1);
    }
}
void makeb(int fat, int u, int j){
    f[u][1] = fat;
    if(dis[u] >= 1<<j) f[u][j] = f[f[f[u][j-1]][1]][j-1];
    for(int now = head[u];  now; now = nxt[now]){
        int  v = vet[now];
        if(v == fat) continue;
        makeb(u, v, j);
    }
}
int  LCA(int u, int v){
    if (dis[u] < dis[v]) swap(u, v); 
    int  maxjump = 0;
    while (1 << (maxjump + 1) <= dis[u]) ++maxjump;
    maxjump += 1;
    for (int j = maxjump; j >= 1; j--) 
        if (dis[u] - (1 << j) + 1 >= dis[v]) 
            u = f[u][j];
    if (u == v) return u; 
    for (int j = maxjump; j >= 1; j--) {
        if (f[u][j] != f[v][j]) {
            u = f[u][j];
            v = f[v][j];
        }
    }
    return f[u][1]; 
}
int main(){
    scanf("%d", &Case);
    while(Case--){
        scanf("%d%d%d", &n, &m, &c);
        for(int i = 1; i <= n; i++)
            fa[i] = i;
        for(int i = 1; i <= m; i++){
            scanf("%d%d%d", &x, &y, &d);
            add(x, y, d);
            add(y, x, d);
            int  fx = findfa(x), fy = findfa(y);
            if(fx != fy) fa[fy] = fx;
        }
        for(int i = 1; i <= n; i++)
            if(fa[i] == i){
                make(0, i, 1);
                for(int j = 2; j <= 20; j++)
                    makeb(0, i, j);
            }
        for(int i = 1; i <= c; i++){
            scanf("%d%d", &x, &y);
            int  fx = findfa(x), fy = findfa(y);
            if(fx != fy){
                printf("Not connected\n");
                continue;
            }
            int  lc = LCA(x, y);
            int  ans = road[x] + road[y] - 2*road[lc];
            printf("%d\n", ans);
        }
        memset(fa, 0, sizeof(fa));
        memset(road, 0, sizeof(road));
        memset(dis, 0, sizeof(dis));
        memset(nxt, 0, sizeof(nxt));
        memset(head, 0, sizeof(head));
        memset(lo, 0, sizeof(lo));
        memset(f, 0, sizeof(fa));
        memset(vet, 0, sizeof(vet));
        num = 0;
    }
    return 0;
}