POJ 2874 LCA 树上任意两点距离

本题说了是无环图，所以就是一片森林了。 而对于树上的任意两点，我们可以用LCA求其距离。距离为两个子节点到根的距离和减去最近祖先到根的距离的2倍。具体画图便可看出来。

并且图是无向图，所以LCA时需要进行标记

POJ 1986同这道题 基本一样

/*
ID: CUGB-wwj
PROG:
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 1111111111
#define MAXN 10005
#define MAXM 1000005
#define L(x) x<<1
#define R(x) x<<1|1
#define eps 1e-4
using namespace std;
struct node
{
    int v, w;
    node(){}
    node(int a, int b){ v = a; w = b;}
};
vector<node>tree[MAXN], ask[MAXN];  //tree里w代表权值，ask里w代表序号
int dis[MAXN], father[MAXN], vis[MAXN], ans[MAXM];
int n, m, c;
void init()
{
    for(int i = 0; i <= n; i++)
    {
        dis[i] = 0;
        father[i] = i;
        vis[i] = 0;
        tree[i].clear();
        ask[i].clear();
    }
}
int find(int x)
{
    if(father[x] == x) return x;
    int t = find(father[x]);
    father[x] = t;
    return t;
}
void LCA(int u, int w, int root)
{
    dis[u] = w;
    father[u] = u;
    vis[u] = root;
    int size = tree[u].size();
    for(int i = 0; i < size; i++)
    {
        if(!vis[tree[u][i].v])
        {
            LCA(tree[u][i].v, tree[u][i].w + w, root);
            father[tree[u][i].v] = u;
        }
    }
    size = ask[u].size();
    for(int i = 0; i < size; i++)
    {
        if(vis[ask[u][i].v])
        {
            if(vis[ask[u][i].v] == root)
            ans[ask[u][i].w] = dis[u] + dis[ask[u][i].v] - 2 * dis[find(ask[u][i].v)];
            else ans[ask[u][i].w] = -1;
        }
    }
}
int main()
{
    int u, v, w;
    while(scanf("%d%d%d", &n, &m, &c) != EOF)
    {
        init();
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            node tmp1(v, w);
            node tmp2(u, w);
            tree[u].push_back(tmp1);
            tree[v].push_back(tmp2);
        }
        for(int i = 1; i <= c; i++)
        {
            scanf("%d%d", &u, &v);
            node tmp1(v, i);
            node tmp2(u, i);
            ask[u].push_back(tmp1);
            ask[v].push_back(tmp2);
        }
        for(int i = 1; i <= n; i++)
        {
            if(!vis[i]) LCA(i, 0, i);
        }
        for(int i = 1; i <= c; i++)
        {
            if(ans[i] == -1) printf("Not connected\n");
            else printf("%d\n", ans[i]);
        }
    }
    return 0;
}