题目描述 小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上去搞基，但是作为两只虫子，他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同），他们想找出一条花费精力最短的路，以使得搞基的时候精力旺盛，他们找到你要你设计一个程序来找到这条路，要求你告诉他们最少需要花费多少精力
输入描述 第一行一个n，接下来n-1行每一行有三个整数u，v, c 。表示节点 u 爬到节点 v 需要花费 c 的精力。 第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u ，v 表示两只虫子所在的节点 输出描述 一共有m行，每一行一个整数，表示对于该次询问所得出的最短距离。
样例输入 3 1 0 1 2 0 1 3 1 0 2 0 1 2
样例输出 1 1 2
数据范围及提示 1<=n<=50000， 1<=m<=75000， 0<=c<=1000
分析 这道题用了Tarjan算法求最近公共祖先（LCA）。Tarjan算法是一种离线算法，即先读入所有的询问（求一次LCA叫做一次询问），然后重新组织查询处理顺序以便得到更高效的处理方法。它结合了深度优先遍历和并查集，整个算法为线性处理时间。 Tarjan算法讲解 https://baike.baidu.com/item/LCA/20414490?fr=aladdin
#include<iostream> #include<vector> #include<cstdio> using namespace std; #define N 50000 + 10//最大顶点数 #define M 75000 + 10//最大询问次数 int n,m;//顶点个数，询问次数 int f[N];//节点的父亲 int vis[N];//访问标志 int sum[N],ans[M]; struct T { int v,c; }; struct Q { int v,id; }; vector<T> e[N]; //树的邻接表（不一定是二叉树） vector<Q> q[M]; //所有查询的内容 void inputTree() //输入树 { scanf("%d",&n); //树的顶点数 int u,v,c; for(int i = 1; i < n; i++) {//输入n-1条树边 scanf("%d%d%d",&u,&v,&c); T t; t.v = v,t.c = c; e[u].push_back(t); t.v = u; e[v].push_back(t); } } void inputQuires() //输入查询 { scanf("%d",&m); //查询个数 for(int i = 0; i < m; i++) { int u,v; scanf("%d%d",&u,&v); //查询u和v的LCA Q t; t.v = v,t.id = i; q[u].push_back(t);//双向询问，保证完整性 t.v = u; q[v].push_back(t); } } void init() //初始化 { for(int i = 0; i < n; i++) f[i] = i; } int find(int x) //查找 { if (x != f[x]) f[x] = find(f[x]); return f[x]; } void tarjan(int u,int pre,int val) //Tarjan算法求解LCA { sum[u] = val;//sum[u]表示u到根结点的距离 for (int i = 0; i < e[u].size(); i++) { int v = e[u][i].v; int c = e[u][i].c; if(v != pre) { tarjan(v,u,val + c); f[v] = u; } } vis[u] = 1; //标记为已访问 for (int i = 0; i < q[u].size(); i++) { //与根节点x有关的查询 int v = q[u][i].v; if (vis[v]) {//如果查询的另一个节点已访问，则输出结果 int k = q[u][i].id; int f = find(v); ans[k] = sum[u] + sum[v] - 2 * sum[f]; } } } int main() { inputTree(); //输入树 inputQuires();//输入查询 init(); tarjan(0,-1,0); for(int i = 0; i < m; i++) cout << ans[i] << endl; return 0; }