题目要对每次询问将一个树形图的三个点连接，输出最短距离。
利用tarjan离线算法，算出每次询问的任意两个点的最短公共祖先，并在dfs过程中求出离根的距离。把每次询问的三个点两两求出最短距离，这样最终结果就是3个值一半。
其实开始我用的一种很挫的方法才AC的，具体思路就不说了，感觉很麻烦又不好写的样子。怎么没想到上面的简便方法呢。
初始代码：
#include <iostream>
#include <sstream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <string>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define esp 1e-6
#define pi acos(-1.0)
#define pb push_back
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define mp(a, b) make_pair((a), (b))
#define in freopen("in.txt", "r", stdin);
#define out freopen("out.txt", "w", stdout);
#define print(a) printf("%d\n",(a));
#define bug puts("********))))))");
#define stop system("pause");
#define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++)
#define inf 0x0f0f0f0f using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VII;
typedef vector<pii, int> VIII;
typedef VI:: iterator IT;
const int maxn = + ;
const int maxm = ( + ) * ;
int dis[maxn], lin[maxm][], vis[maxn], pa[maxn];
VII g[maxn];
VII query[maxn];
int n, m;
int findset(int x)
{
return pa[x] == x? x : pa[x] = findset(pa[x]);
}
void tarjan(int u)
{
vis[u] = ;
pa[u] = u;
for(int i = ; i < (int)query[u].size(); i++)
{
int v= query[u][i].first;
if(vis[v])
{
lin[query[u][i].second][] = findset(v);
}
}
for(int i = ; i < (int)g[u].size(); i++)
{
int v = g[u][i].second;
if(!vis[v])
{
dis[v] = dis[u] + g[u][i].first;
tarjan(v);
pa[v] = u;
}
}
}
void Init(void)
{
for(int i = ; i < maxn; i++)
query[i].clear(), g[i].clear();
memset(vis, , sizeof(vis));
}
int main(void)
{
int flag = ;
while(scanf("%d", &n) == )
{
if(flag) puts("");
else flag = ;
Init();
for(int i = ; i < n; i++)
{
int u, v, len;
scanf("%d%d%d", &u, &v, &len);
g[u].pb(mp(len, v));
g[v].pb(mp(len, u));
}
scanf("%d", &m);
for(int i = ; i <= *m; i += )
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
query[lin[i][] = x].pb(mp(lin[i][] = y, i));
query[lin[i][]].pb(mp(lin[i][], i));
query[lin[i+][] = x].pb(mp(lin[i+][] = z, i+));
query[lin[i+][]].pb(mp(lin[i+][], i+));
query[lin[i+][] = y].pb(mp(lin[i+][] = z, i+));
query[lin[i+][]].pb(mp(lin[i+][], i+));
}
dis[] = ;
tarjan();
for(int i = ; i <= *m; i += )
{
int ans;
if(lin[i+][] == lin[i+][])
{
// if(lin[i+2][2] == 0)
// ans = dis[lin[i][0]] + dis[lin[i][1]] - 2 * dis[lin[i][2]] + dis[lin[i][2]] + dis[lin[i+1][1]];
ans = dis[lin[i][]] + dis[lin[i][]] - * dis[lin[i][]] - *dis[lin[i+][]] + dis[lin[i+][]] + dis[lin[i][]];
}
else
ans = dis[lin[i][]] + dis[lin[i][]] - * dis[lin[i][]] + dis[lin[i+][]]- max(dis[lin[i+][]], dis[lin[i+][]]);
printf("%d\n",ans);
}
}
return ;
}
简便方法的代码：
#include <iostream>
#include <sstream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <string>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define esp 1e-6
#define pi acos(-1.0)
#define pb push_back
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define mp(a, b) make_pair((a), (b))
#define in freopen("in.txt", "r", stdin);
#define out freopen("out.txt", "w", stdout);
#define print(a) printf("%d\n",(a));
#define bug puts("********))))))");
#define stop system("pause");
#define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++)
#define inf 0x0f0f0f0f using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VII;
typedef vector<pii, int> VIII;
typedef VI:: iterator IT;
const int maxn = + ;
const int maxm = ( + ) * ;
int dis[maxn], lin[maxm][], vis[maxn], pa[maxn];
VII g[maxn];
VII query[maxn];
int ans[maxm];
int n, m;
int findset(int x)
{
return pa[x] == x? x : pa[x] = findset(pa[x]);
}
void tarjan(int u)
{
vis[u] = ;
pa[u] = u;
for(int i = ; i < (int)query[u].size(); i++)
{
int v= query[u][i].first;
if(vis[v])
{
ans[query[u][i].second] += dis[u] + dis[v] - * dis[findset(v)];
}
}
for(int i = ; i < (int)g[u].size(); i++)
{
int v = g[u][i].second;
if(!vis[v])
{
dis[v] = dis[u] + g[u][i].first;
tarjan(v);
pa[v] = u;
}
}
}
void Init(void)
{
for(int i = ; i < maxn; i++)
query[i].clear(), g[i].clear();
memset(vis, , sizeof(vis));
memset(ans, , sizeof(ans));
}
int main(void)
{
int flag = ;
while(scanf("%d", &n) == )
{
if(flag) puts("");
else flag = ;
Init();
for(int i = ; i < n; i++)
{
int u, v, len;
scanf("%d%d%d", &u, &v, &len);
g[u].pb(mp(len, v));
g[v].pb(mp(len, u));
}
scanf("%d", &m);
for(int i = ; i <= m; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
query[x].pb(mp(y, i));
query[y].pb(mp(x, i));
query[x].pb(mp(z, i));
query[z].pb(mp(x, i));
query[y].pb(mp(z, i));
query[z].pb(mp(y, i));
}
dis[] = ;
tarjan();
for(int i = ; i <= m; i++)
{
printf("%d\n", ans[i]>>);
}
}
return ;
}