例题1

http://hihocoder.com/problemset/problem/1067

给出n行父-子的名字，q个询问，输出最近公共祖先

程序代码

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 100050;
vector<int> g[maxn];
vector<int> q[maxn];
vector<int> num[maxn];
int ans[maxn];
int n, Q;
map<string,int> dict;
vector<string> v;
int fa[maxn], r[maxn], ind[maxn];
bool vis[maxn];
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
void Union(int u, int v){
    u = find(u);
    v = find(v);
    if(u != v) 
        fa[v] = u;
}
void dfs(int u){
    fa[u] = u;
    for(int i = 0; i < g[u].size(); i++){
        int v = g[u][i];
        dfs(v);
        Union(u,v);
    }
        vis[u] = true;
    for(int i = 0; i < q[u].size(); i++){
        int v = q[u][i];
        if(vis[v]){
            ans[num[u][i]] = fa[find(v)];
        }
    }
}
int main(){
//freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 0; i < maxn; i++) fa[i] = i;
    string str1, str2;
    int tot = 0;
    for(int i = 0; i < n; i++){
        cin >> str1 >> str2;
        if(dict.count(str1) == 0){
            dict[str1] = tot;
            v.pb(str1);
            tot++;
        }
        if(dict.count(str2) == 0){
            dict[str2] = tot;
            v.pb(str2);
            tot++;
        }
        int u = dict[str1];
        int v = dict[str2];
        g[u].pb(v);
        ind[v]++;
    }
    cin >> Q;
    for(int i = 0; i < Q; i++){
        cin >> str1 >> str2;
        int u = dict[str1];
        int v = dict[str2];
        q[u].pb(v);
        q[v].pb(u);
        num[u].pb(i);
        num[v].pb(i);
    }
    int i;
    for(i = 0; i < n; i++)if(ind[i] == 0) break;
    dfs(i);
    for(int i = 0; i < Q; i++) cout << v[ans[i]] << endl;
    return 0;
}

例题2

http://acm.hdu.edu.cn/showproblem.php?pid=2586

程序代码

#include <bits/stdc++.h>
typedef long long ll;
#define fi first
#define se second
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define inf  300000
using namespace std;
const int maxn = 40005;
int T, n, m;
bool vis[maxn];
int f[maxn], ans[maxn], dis[maxn];
vector<int> g[maxn];
vector<int> w[maxn];
vector<int> q[maxn];
vector<int> num[maxn];
void Init(){
    for(int i = 0; i < maxn; i++){
        g[i].clear();
        w[i].clear();
        q[i].clear();
        num[i].clear();
        vis[i] = false;
        dis[i] = 0;
    }
}
int find(int x){return f[x] == x ? x : f[x] = find(f[x]);}
void Union(int u, int v){
    u = find(u);
    v = find(v);
    if(u != v)
        f[v] = u;
}
void dfs(int u, int val){
    dis[u] = val; vis[u] = true; f[u] = u;
    for(int i = 0; i < g[u].size(); i++){
        int v = g[u][i];
        if(vis[v]) continue;
        dfs(v, w[u][i]+val);
        Union(u,v);
    }
    for(int i = 0; i < q[u].size(); i++){
        int v = q[u][i];
        if(vis[v]) ans[num[u][i]] = dis[u] + dis[v] - 2 * dis[find(v)];
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while(T--){
        Init();
        cin >> n >> m;
        int u, we, v;
        for(int i = 0; i < n-1; i++){
            cin >> u >> v >> we;
            g[u].pb(v);
            g[v].pb(u);
            w[u].pb(we);
            w[v].pb(we);
        }
        for(int i = 0; i < m; i++){
            cin >> u >> v;
            q[u].pb(v);
            q[v].pb(u);
            num[u].pb(i);
            num[v].pb(i);
        }
        dfs(1,0);
        for(int i = 0; i < m; i++) cout << ans[i] << "\n";
    }
    return 0;
}